Cod sursa(job #367683)

Utilizator PavelRazvanPavel Razvan PavelRazvan Data 23 noiembrie 2009 10:10:21
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 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];
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;
    viz[x]=1;
    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;
    ++viz[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;
}