Cod sursa(job #2055364)

Utilizator DawlauAndrei Blahovici Dawlau Data 3 noiembrie 2017 09:45:38
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 kb
#include<fstream>
#include<bitset>
#include<list>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
const int NMAX=100005;
list<int>g[NMAX],gt[NMAX],ans[NMAX];
int topo_sort[NMAX],n,m,k;
bitset<NMAX>vis;
void read_data(){
    int from,to;
    fin>>n>>m;
    while(m--){
        fin>>from>>to;
        g[from].push_back(to);
        gt[to].push_back(from);
    }
}
void DFS(int node){
    vis[node]=true;
    list<int>::iterator it;
    for(it=g[node].begin();it!=g[node].end();++it)
        if(!vis[*it])
            DFS(*it);
    topo_sort[++k]=node;
}
void topological_sort(){
    int i;
    for(i=1;i<=n;++i)
        if(!vis[i])
            DFS(i);
    vis.reset();
    k=0;
}
void DFS2(int node){
    vis[node]=true;
    ans[k].push_back(node);
    list<int>::iterator it;
    for(it=gt[node].begin();it!=gt[node].end();++it)
        if(!vis[*it])
            DFS2(*it);
}
void kosaraju(){
    int i;
    for(i=n;i>=1;--i)
        if(!vis[topo_sort[i]]){
            ++k;
            DFS2(topo_sort[i]);
        }
}
void print(){
    int i;
    list<int>::iterator it;
    fout<<k<<'\n';
    for(i=1;i<=k;++i){
        for(it=ans[i].begin();it!=ans[i].end();++it)
            fout<<*it<<' ';
        fout<<'\n';
    }
}
int main(){
    read_data();
    topological_sort();
    kosaraju();
    print();
}