Cod sursa(job #323089)

Utilizator ProcopliucProcopliuc Adrian Procopliuc Data 10 iunie 2009 18:03:15
Problema Componente tare conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
# include <stdio.h>
int s[1001],i,j,n,m,k,x,y,x1,x2,q,w,d[1001];
struct nod
{
int info;
nod *urm;
}*a[1001],*b[1001],*p,*v,*c[1001];


void df1 (int x)
{
nod *p;
w++;
d[w]=x;
p=a[x];
s[x]=i;

while (p)
{
if (s[p->info]==0)
df1 (p->info);

p=p->urm;
}
}




void df (int x)
{

nod *p;
s[x]=0;
p=b[x];
b[x]=0;
a[x]=0;
v=new nod;
v->info=x;
v->urm=c[k];
c[k]=v;

while (p)
{
if (s[p->info]!=0 && s[p->info]==y)
df (p->info);


p=p->urm;
}


}

int main ()
{
freopen ("ctc.in","r",stdin);
freopen ("ctc.out","w",stdout);
scanf ("%i%i",&n,&m);
for (i=1;i<=m;i++)
{
scanf ("%i%i",&x,&y);

p=new nod;
p->info=y;
p->urm=a[x];
a[x]=p;

p=new nod;
p->info=x;
p->urm=b[y];
b[y]=p;
}


for (i=1;i<=n;i++)
{
if (s[i]==0)
df1 (i);
}

for (j=1;j<=n;j++)
if (s[d[j]]!=0)
{
y=s[d[j]];
k++;
df (d[j]);

}





printf ("%i\n",k);

for (i=1;i<=k;i++)
{
while (c[i])
{
printf ("%i ",c[i]->info);
c[i]=c[i]->urm;
}
printf ("\n");
}
return 0;

}