Cod sursa(job #407596)

Utilizator hasegandaniHasegan Daniel hasegandani Data 2 martie 2010 14:41:07
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include<stdio.h>
#include<vector>

using namespace std;

#define Nmax 100010

vector <int> l[Nmax],lt[Nmax];

int N,v[Nmax],ord[Nmax],K;
int c[Nmax],Nr,comp[Nmax];

void DF(int k)
{
    v[k]=1;

    for(int i=0;i<(int)l[k].size();++i)
        if (!v[ l[k][i] ])
            DF( l[k][i] );
    ++K;
    ord[N-K+1]=k;
}

void DFt(int k)
{
    v[k]=1;

    for(int i=0;i<(int)lt[k].size();++i)
        if (!v[ lt[k][i] ])
            DFt( lt[k][i] );
    c[++K]=k;
}

void solve()
{
    for(int i=1;i<=N;++i)
        if (!v[i])
            DF(i);

    K=0;
    memset(v,0,sizeof(v));

    for(int i=1;i<=N;++i)
        if (!v[ ord[i] ])
            {
            comp[++Nr]=K+1;
            DFt(ord[i]);
            }

    printf("%d\n",Nr);
    comp[++Nr]=K+1;
    for(int i=1;i<Nr;++i)
        {
        for(int j=comp[i];j<comp[i+1];++j)
            printf("%d ",c[j]);
        printf("\n");
        }
}

void cit();

int main()
{
    cit();
    solve();
    return 0;
}

void cit()
{
    int M,a,b;
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);
    scanf("%d%d",&N,&M);
    for( ; M ;--M)
        {
        scanf("%d%d",&a,&b);
        l[a].push_back(b);
        lt[b].push_back(a);
        }
}