Cod sursa(job #373269)

Utilizator PavelRazvanPavel Razvan PavelRazvan Data 13 decembrie 2009 10:35:49
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.32 kb
#include<stdio.h>
#define DIM 200005
#define DIM2 100005
struct nod
{
    int x;
    nod *urm;
} *lst[DIM],*lst2[DIM];
int n,vf,a[DIM2/20][DIM2/20],viz[DIM2],c[DIM/20],dr;
void add (int a,int b)
{
    nod *p=new nod;
    p->x=b;
    p->urm=lst[a];
    lst[a]=p;
}
void add2 (int a,int b)
{
    nod *p=new nod;
    p->x=b;
    p->urm=lst2[a];
    lst2[a]=p;
}
void read ()
{
    int i,x,y,m;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;++i)
        scanf("%d%d",&x,&y),add(x,y),add2(y,x);
}
void df1 (int x)
{
    nod *p;
    viz[x]=1;
    for(p=lst[x];p;p=p->urm)
        if(viz[p->x]==0)
            df1(p->x);
}
void df2 (int x)
{
    nod *p;
    ++viz[x];
    c[++dr]=x;
    for(p=lst2[x];p;p=p->urm)
        if(viz[p->x]==1)
            df2(p->x);
}
void solve (int x)
{
    int i;
    dr=0;
    df1(x);
    df2(x);
    a[++vf][0]=dr;
    for(i=1;i<=a[vf][0];++i)
        a[vf][i]=c[i];
    for(i=1;i<=n;++i)
        if(viz[i]==1)
            viz[i]=0;
}
int main ()
{
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);
    read ();
    int i,j;
    for(i=1;i<=n;++i)
        if(!viz[i])
            solve (i);
    printf("%d\n",vf);
    for(i=1;i<=vf;++i,printf("\n"))
        for(j=1;j<=a[i][0];++j)
            printf("%d ",a[i][j]);
    return 0;
}