Cod sursa(job #2118102)

Utilizator DawlauAndrei Blahovici Dawlau Data 30 ianuarie 2018 02:32:06
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.86 kb
#include<fstream>
#include<list>
#include<stack>
#include<bitset>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
const int NMAX = 100005;

list<int> graph[NMAX], SCC[NMAX];
stack<int> Stack;
bitset<NMAX> inStack;

int nodesCount, edgesCount, traversalMoment, SCCCount;
int link[NMAX], lowLink[NMAX];

inline void read_data(){

    fin >> nodesCount >> edgesCount;

    int from, to;
    while(edgesCount--){

        fin >> from >> to;
        graph[from].push_back(to);
    }
}

inline void getNewSCC(int node){

    ++SCCCount;

    int topOfTheStack;
    do{

        topOfTheStack = Stack.top();
        inStack[topOfTheStack] = false;
        Stack.pop();
        SCC[SCCCount].push_back(topOfTheStack);

    }while(node != topOfTheStack);

}

void getSCC(int node){

    link[node] = lowLink[node] = ++traversalMoment;
    Stack.push(node);
    inStack[node] = true;

    list<int>::iterator nextNode;
    for(nextNode = graph[node].begin(); nextNode != graph[node].end(); ++nextNode)
        if(link[*nextNode] == 0){

            getSCC(*nextNode);
            lowLink[node] = min(lowLink[node], lowLink[*nextNode]);
        }
        else if(inStack[*nextNode])
            lowLink[node] = min(lowLink[node], lowLink[*nextNode]);

    if(link[node] == lowLink[node])
        getNewSCC(node);
}

inline void solve(){

    int node;
    for(node = 1; node <= nodesCount; ++node)
        if(link[node] == 0)
            getSCC(node);
}

inline void printSCC(){

    fout << SCCCount << '\n';

    int index;
    list<int>::iterator node;
    for(index = 1; index <= SCCCount; ++index){

        for(node = SCC[index].begin(); node != SCC[index].end(); ++node)
            fout << *node << ' ';
        fout << '\n';
    }
}
int main(){

    read_data();
    solve();
    printSCC();
}