Cod sursa(job #367667)

Utilizator PavelRazvanPavel Razvan PavelRazvan Data 23 noiembrie 2009 09:54:11
Problema Componente tare conexe Scor 12
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 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/8][DIM2/8],viz[DIM2];
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 solve (int x)
{
    int st,dr,i,c[DIM];
    nod *p;
    c[st=dr=1]=x;
    while(st<=dr)
    {
        for(p=lst[c[st]];p;p=p->urm)
            if(!viz[p->x])
            {
                c[++dr]=p->x;
                viz[p->x]=1;
            }
        ++st;
    }
    c[st=dr=1]=x;
    while(st<=dr)
    {
        for(p=lst2[c[st]];p;p=p->urm)
            if(viz[p->x]==1)
            {
                c[++dr]=p->x;
                ++viz[p->x];
            }
        ++st;
    }
    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;
}