Cod sursa(job #1089376)

Utilizator FayedStratulat Alexandru Fayed Data 21 ianuarie 2014 17:40:52
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.52 kb
#include <cstdio>
#include <vector>
#define NMAX 100001
using namespace std;

bool vizitat[NMAX];
int n,m,nr;
int k;

vector < vector < int > > Graf;
vector < vector < int > > Graft;
vector < int > M[NMAX];

int postordine[NMAX];

inline void read(){

    int x,y;
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);
    scanf("%d%d",&n,&m);
    Graf.resize(n+1);
    Graft.resize(n+1);

    for(register int i=1;i<=m;++i){

        scanf("%d%d",&x,&y);
        Graf[x].push_back(y);
        Graft[y].push_back(x);
    }
}

void DFS(int nod){

    vizitat[nod] = 1;
    for(vector <int> :: iterator it = Graf[nod].begin();it!=Graf[nod].end();++it)
        if(!vizitat[*it])
            DFS(*it);

postordine[++k] = nod;
}

void DFST(int nod){

    vizitat[nod] = 0;
    M[nr].push_back(nod);

    for(vector < int > ::iterator it = Graft[nod].begin();it!=Graft[nod].end();++it)
        if(vizitat[*it])
            DFST(*it);
}

void solve(){

    for(register int i=1;i<=n;++i)
        if(!vizitat[i])
            DFS(i);

    for(register int i=n;i>0;--i){

        if(vizitat[postordine[i]]){

            ++nr;
            DFST(postordine[i]);
        }

    }
}

void write(){

    int length;
    printf("%d\n",nr);
    for(register int i=1;i<=nr;++i){
       length = M[i].size();
        for(register int j=0;j<length;++j)
             printf("%d ",M[i][j]);
             printf("\n");
    }
}

int main(){

read();
solve();
write();

return 0;
}