Cod sursa(job #397035)

Utilizator BooZZySandu Bogdan BooZZy Data 16 februarie 2010 11:29:45
Problema Componente tare conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include<stdio.h>
int suc[100000],prd[100000],i,j,nrc,x,y,n,m;
struct nod
{
	int inf;
	nod *adr;
};
nod *l[100000],*d[100000],*p,*u;
void succ(int no)
{
	nod *c;
	suc[no]=nrc;
	c=l[no];
	while(c)
	{
		if(!suc[c->inf])
			succ(c->inf);
		c=c->adr;
	}
}
void pred(int no)
{
	nod *c;
	prd[no]=nrc;
	c=d[no];
	while(c)
	{
		if(!prd[c->inf])
			pred(c->inf);
		c=c->adr;
	}
}
int main()
{
	freopen("ctc.in","r",stdin);
	freopen("ctc.out","w",stdout);
	scanf("%d %d",&n,&m);
	for(i=0;i<m;i++)
	{
		scanf("%d %d",&x,&y);
		p=new nod;
		p->adr=l[x];
		p->inf=y;
		l[x]=p;
		p=new nod;
		p->adr=d[y];
		p->inf=x;
		d[y]=p;
	}
	nrc=1;
	for(i=1;i<=n;i++)
		if(!suc[i])
		{
			suc[i]=nrc;
			succ(i);
			pred(i);
			for(j=1;j<=n;j++)
				if(suc[j]!=prd[j])
					suc[j]=prd[j]=0;
			nrc++;
		}
	printf("%d\n",nrc-1);
	for(i=1;i<nrc;i++)
	{
		for(j=1;j<=n;j++)
			if(suc[j]==i)
				printf("%d ",j);
		printf("\n");
	}
	return 0;
}