Cod sursa(job #280007)

Utilizator mircea_infoSuciu Mircea-Gabriel mircea_info Data 13 martie 2009 10:00:19
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
//ctc bc

#include <stdio.h>
#include <string.h>
#define maxn 100001

struct nod {int inf; nod *urm;} *g[maxn],*gt[maxn],*l[maxn];
int n,m,st[maxn],viz[maxn];
int nrsol;

void baga(int x, int y)
{
	nod *q=new nod;
	q->inf=y;
	q->urm=g[x];
	g[x]=q;
	q=new nod;
	q->inf=x;
	q->urm=gt[y];
	gt[y]=q;
}

void parc1(int x)
{
	viz[x]=1;
	for(nod *i=g[x];i;i=i->urm)
		if(!viz[i->inf])
			parc1(i->inf);
	st[++st[0]]=x;
}

void parc2(int x)
{
	viz[x]=1;
	nod *q=new nod;
	q->inf=x;
	q->urm=l[nrsol];
	l[nrsol]=q;
	for(q=gt[x];q;q=q->urm)
		if(!viz[q->inf])
			parc2(q->inf);
}

int main()
{
	freopen("ctc.in","r",stdin);
	freopen("ctc.out","w",stdout);
	scanf("%d%d",&n,&m);
	int x,y,i;
	for(i=1;i<=m;i++)
	{
		scanf("%d%d",&x,&y);
		baga(x,y);
	}
	for(i=1;i<=n;i++)
		if(!viz[i])
			parc1(i);
	memset(viz,0,sizeof(viz));
	for(i=n;i>=0;i--)
		if(!viz[st[i]])
		{
			nrsol++;
			parc2(st[i]);
		}
	printf("%d\n",nrsol);
	for(i=1;i<=nrsol;i++)
	{
		for(nod *q=l[i];q;q=q->urm)
			printf("%d ",q->inf);
		printf("\n");
	}
	fclose(stdout);
	return 0;
}