Cod sursa(job #2664050)

Utilizator DawlauAndrei Blahovici Dawlau Data 27 octombrie 2020 20:26:22
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.51 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("ctc.in");
ofstream fout("ctc.out");

const int Inf = INT_MAX;

vector < vector <int> > g, comps;
vector <int> lowlink, pre;
int V, E;

int traversalOrd;

stack <int> Stack;

void readGraph(){

    fin >> V >> E;

    g.resize(V + 1);
    lowlink.resize(V + 1);
    pre.resize(V + 1);
    comps.reserve(V);

    for(int e = 0; e < E; ++e){

        int from, to;
        fin >> from >> to;

        g[from].push_back(to);
    }
}


void cacheSCC(int node){

    vector <int> SCC;
    SCC.reserve(V);

    int stackNode;
    do{

        stackNode = Stack.top();
        Stack.pop();

        lowlink[stackNode] = Inf; // for cross edges
        SCC.push_back(stackNode);
    }while(stackNode != node);

    comps.push_back(SCC);
}


void DFS(int node){

    lowlink[node] = pre[node] = ++traversalOrd;
    Stack.push(node);

    for(const int &adj : g[node])
        if(lowlink[adj] == 0){ // fwd edge

            DFS(adj);
            lowlink[node] = min(lowlink[node], lowlink[adj]);
        }
        else lowlink[node] = min(lowlink[node], lowlink[adj]); // back edge or cross edge

    if(lowlink[node] == pre[node])
        cacheSCC(node);
}


int main(){

    readGraph();

    for(int node = 1; node <= V; ++node)
        if(lowlink[node] == 0)
            DFS(node);


    // printing

    fout << comps.size() << '\n';
    for(int c = 0; c < (int)comps.size(); ++c){

        for(const int &node : comps[c])
            fout << node << ' ';
        fout << '\n';
    }
}