Cod sursa(job #1564023)

Utilizator 2chainzTauheed Epps 2chainz Data 7 ianuarie 2016 20:12:04
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include<fstream>
#include<algorithm>
#include<vector>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
const int Nmax = 100001;
vector<int> G[Nmax],Gt[Nmax],C[Nmax];
int N,M,K,m[Nmax],f[Nmax];
void dfs1(int x){m[x]=1;for(vector<int>::iterator it=G[x].begin();it!=G[x].end();++it) if(!m[*it]) dfs1(*it);f[++f[0]]=x;}
void dfs2(int x){C[K].push_back(x);m[x]=1;for(vector<int>::iterator it=Gt[x].begin();it!=Gt[x].end();++it) if(!m[*it]) dfs2(*it);}
int main(){
    in>>N>>M;
    for(int i=1;i<=M;i++){
        int x,y;
        in>>x>>y;
        G[x].push_back(y);
        Gt[y].push_back(x);
    }
    for(int i=1;i<=N;i++) if(!m[i]) dfs1(i);
    for(int i=1;i<=N;i++) m[i]=0;
    for(int i=N;i>=1;i--) if(!m[f[i]]) K++,dfs2(f[i]);
    out<<K<<'\n';
    for(int i=1;i<=K;i++){
        sort(C[i].begin(),C[i].end());
        for(vector<int>::iterator it=C[i].begin();it!=C[i].end();++it) out<<*it<<' ';
        out<<'\n';
    }
    return 0;
}