Cod sursa(job #373271)

Utilizator PavelRazvanPavel Razvan PavelRazvan Data 13 decembrie 2009 10:42:36
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 kb
#include<stdio.h>
#define DIM 200005
#define DIM2 100005
struct nod
{
    int x;
    nod *urm;
} *lst[DIM],*lst2[DIM],*rez[DIM];
int n,vf,viz[DIM2],c[DIM],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 add3 (int a,int b)
{
    nod *p=new nod;
    p->x=b;
    p->urm=rez[a];
    rez[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);
    ++vf;
    for(i=1;i<=dr;++i)
        add3(vf,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;
    nod *p;
    for(i=1;i<=n;++i)
        if(!viz[i])
            solve (i);
    printf("%d\n",vf);
    for(i=1;i<=vf;++i,printf("\n"))
        for(p=rez[i];p;p=p->urm)
            printf("%d ",p->x);
    return 0;
}