Cod sursa(job #235716)

Utilizator crawlerPuni Andrei Paul crawler Data 25 decembrie 2008 14:50:28
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include <stdio.h>

#define Nmax 100024

typedef struct nod_ { int a; nod_*x;} *pNod;
pNod l[Nmax], l2[Nmax], comp[Nmax];

int post[Nmax],n,m,cnt;
char v[Nmax];

void df(int nod)
{
     v[nod] = 1;
     for (pNod it=l[nod];it;it=it->x) 
     if (v[it->a]==0) df(it->a);     
     post[++post[0]] = nod;
}

void df2(int nod)
{
     v[nod] = 0;
     pNod q = new nod_;
     q->a = nod;
     q->x = comp[cnt];
     comp[cnt] = q;     
     for (pNod it=l2[nod];it;it=it->x) 
     if (v[it->a]==1) df2(it->a);     
}

int main()
{
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);
    
    scanf("%d%d",&n,&m);
    
    pNod q;
    int A,B;
    for (int i=1;i<=m;++i)
    {
        scanf("%d%d",&A,&B);
        q = new nod_;
        q->a=B;
        q->x=l[A];
        l[A]=q;    

        q = new nod_;
        q->a=A;
        q->x=l2[B];
        l2[B]=q;    
    }   

    for (int i=1;i<=n;++i)
    if (v[i] == 0) df(i);

    for (int i=n;i>0;--i)
    if (v[post[i]] == 1) { ++cnt; df2(post[i]); }    
    
    printf("%d\n", cnt);
    for (int i=1;i<=cnt;++i,printf("\n"))
    for (pNod it=comp[i];it;it=it->x) printf("%d ", it->a);
        
    return 0;
}