Cod sursa(job #1016577)

Utilizator teoionescuIonescu Teodor teoionescu Data 26 octombrie 2013 14:39:31
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include<fstream>
#include<vector>
#include<cstring>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
const int Nmax = 100005;
int N,M;
int mark[Nmax],f[2*Nmax],t;
vector<int> G[Nmax],GT[Nmax];
vector<int> C[Nmax]; int nc;
void dfs(int i){
    mark[i]=1;
    f[++t]=i;
    for(vector<int>::iterator it=G[i].begin();it!=G[i].end();++it) if(!mark[*it]) dfs(*it);
    f[++t]=i;
}
void DFS(int i){
    mark[i]=1;
    C[nc].push_back(i);
    for(vector<int>::iterator it=GT[i].begin();it!=GT[i].end();++it) if(!mark[*it]) DFS(*it);
}
int main(){
    in>>N>>M;
    for(int i=1;i<=M;i++){
        int a,b;
        in>>a>>b;
        G[a].push_back(b);
        GT[b].push_back(a);
    }
    memset(mark,0,sizeof(mark));
    for(int i=1;i<=N;i++) if(!mark[i]) dfs(i);
    memset(mark,0,sizeof(mark));
    for(int i=2*N;i>=1;i--){
        if(!mark[f[i]]){
            nc++;
            DFS(f[i]);
        }
    }
    out<<nc<<'\n';
    for(int i=1;i<=nc;i++){
        for(vector<int>::iterator it=C[i].begin();it!=C[i].end();++it) out<<*it<<' ';
        out<<'\n';
    }
    return 0;
}