Cod sursa(job #2156620)

Utilizator DawlauAndrei Blahovici Dawlau Data 8 martie 2018 21:11:08
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.5 kb
#include<fstream>
#include<list>
#include<bitset>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
const int NMAX = 1e5 + 5;

list<int> adjList[NMAX], adjListTrans[NMAX], SCC[NMAX];
bitset<NMAX> vis;

int Stack[NMAX];
int nodesCnt, edgesCnt, StackLen, SCCCnt;

inline void readData(){

    fin >> nodesCnt >> edgesCnt;

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

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

void topoSort(int node){

    vis[node] = true;
    for(const int &nextNode : adjList[node])
        if(!vis[nextNode])
            topoSort(nextNode);
    Stack[++StackLen] = node;
}

inline void getOrder(){

    int node;
    for(node = 1; node <= nodesCnt; ++node)
        if(!vis[node])
            topoSort(node);
}

void DFS(int node){

    vis[node] = false;
    SCC[SCCCnt].push_back(node);
    for(const int &nextNode : adjListTrans[node])
        if(vis[nextNode])
            DFS(nextNode);
}

inline void getSCC(){

    int idx;
    for(idx = StackLen; idx >= 1; --idx)
        if(vis[Stack[idx]]){

            ++SCCCnt;
            DFS(Stack[idx]);
        }
}

inline void print(){

    fout << SCCCnt << '\n';

    int idx;
    for(idx = 1; idx <= SCCCnt; ++idx){
        for(const int &node : SCC[idx])
            fout << node << ' ';
        fout << '\n';
    }
}

int main(){

    readData();
    getOrder();
    getSCC();
    print();
}