Cod sursa(job #412009)

Utilizator jupanubv92Popescu Marius jupanubv92 Data 5 martie 2010 12:03:22
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include<stdio.h>
#include<vector>
#define Nmx 100005

using namespace std;

int n,m,pre[Nmx],nr,viz[Nmx],nrs;
vector<int> G[Nmx],GT[Nmx],sol[Nmx];

void citire()
{
    scanf("%d%d",&n,&m);
    int x,y;
    for(int i=1;i<=m;++i)
    {
        scanf("%d%d",&x,&y);
        G[x].push_back(y);
        GT[y].push_back(x);
    }
}

void dfs(int x)
{
    viz[x]=1;
    for(int i=0;i<G[x].size();++i)
        if(!viz[G[x][i]])
            dfs(G[x][i]);
    pre[++nr]=x;
}

void dfsT(int x)
{
    viz[x]=0;
    sol[nrs].push_back(x);
    for(int i=0;i<GT[x].size();++i)
        if(viz[GT[x][i]])
            dfsT(GT[x][i]);
}

void solve()
{
    for(int i=1;i<=n;++i)
        if(!viz[i])
            dfs(i);
    for(int i=n;i>=1;--i)
        if(viz[pre[i]])
        {
            nrs++;
            dfsT(pre[i]);
        }
    printf("%d\n",nrs);
    for(int i=1;i<=nrs;++i)
    {
        for(int j=0;j<sol[i].size();++j)
            printf("%d ",sol[i][j]);
        printf("\n");
    }
}

int main()
{
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);
    citire();
    solve();
    return 0;
}