Cod sursa(job #1053313)

Utilizator Al3ks1002Alex Cociorva Al3ks1002 Data 12 decembrie 2013 17:26:49
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include<cstdio>
#include<bitset>
#include<vector>
using namespace std;
int N,M,X,Y,i,Cnt,TSort[100005],T;
bitset<100005> viz;
vector<int> G[100005],GT[100005],Sol[100005];
void DFS(int X)
{
    for(vector<int>::iterator it=G[X].begin();it!=G[X].end();it++)
        if(!viz[*it]) {viz[*it]=1; DFS(*it);}
    TSort[++T]=X;
}
void DFST(int X)
{
    Sol[Cnt].push_back(X);
    for(vector<int>::iterator it=GT[X].begin();it!=GT[X].end();it++)
        if(viz[*it]) {viz[*it]=0; DFST(*it);}
}
int main()
{
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);
    scanf("%d%d",&N,&M);
    for(;M;M--)
    {
        scanf("%d%d",&X,&Y);
        G[X].push_back(Y);
        GT[Y].push_back(X);
    }
    for(i=1;i<=N;i++)
        if(!viz[i]) {viz[i]=1; DFS(i);}
    for(i=N;i;i--)
        if(viz[TSort[i]]) {Cnt++; viz[TSort[i]]=0; DFST(TSort[i]);}
    printf("%d\n",Cnt);
    for(i=1;i<=Cnt;i++,printf("\n"))
        for(vector<int>::iterator it=Sol[i].begin();it!=Sol[i].end();it++) printf("%d ",*it);
    return 0;
}