Cod sursa(job #2927001)

Utilizator Katherine456719Swan Katherine Katherine456719 Data 19 octombrie 2022 10:04:04
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.07 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;


vector<vector<int>> adj_list;
vector<int> indx; //retine indexul atribuit fiecarui nod in urma parcurgerii DFS
//ce numără nodurile în ordinea în care sunt descoperite
vector<int> lowlink;
//lowlink[v] = min { idx[u] | u este accesibil din v }. v rad <=>  lowlink[v] = idx[v]. lowlink[v]
vector <bool> onStack;
stack <int> st;
int id = 0; // da fiecarui nod un id
int sccCount = 0;//contorizeaza componentele tare conexe
vector<vector<int>> scc;

//algoritmul lui tarjan
void dfs(int node){
    st.push(node);
    onStack[node] = true;
    indx[node] = lowlink[node] = ++id;

    //vizitam toti vecinii nodului si calculam min dintre valorile atribuite in lowlink
    for(auto x : adj_list[node]){
        if(indx[x] == -1)
            dfs(x);
        if(onStack[x])
            lowlink[node] = min(lowlink[node], lowlink[x]);
    }

    //dupa ce am vizitat toti vecinii nodului
    //daca suntem la inceputul unei ctc
    //stiva va fi golita pana suntem la inceputul ctc
    if(indx[node] == lowlink[node]){
        vector<int> ctc;
        int nod = st.top();
        while(nod != node){
            st.pop();
            onStack[nod] = false;
            lowlink[nod] = indx[node];
            ctc.push_back(nod);
            nod = st.top();
        }
        st.pop();
        ctc.push_back(node);
        scc.push_back(ctc);
        onStack[node] = false;
        sccCount++;
    }
}

int main(){
    ifstream fin("ctc.in");
    ofstream fout("ctc.out");
    int n,m,x,y;
    fin >> n >> m;
    adj_list.resize(n+1);
    for(int i = 0; i < m; ++i){
        fin >> x >> y;
        adj_list[x].push_back(y);
    }
    indx = vector<int>(n + 1,-1);
    lowlink = vector<int>(n + 1,-1);
    onStack = vector<bool>(n + 1,false);
    for(int i = 1; i < n+1; ++i)
        if(indx[i] == -1)
            dfs(i);
    fout<<sccCount<<"\n";
    for(auto x: scc) {
        for (auto y: x)
            fout << y << " ";
        fout<<"\n";
    }
}