Cod sursa(job #640258)

Utilizator sternvladStern Vlad sternvlad Data 25 noiembrie 2011 01:04:27
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#include <cstdio>
#include <string>
#define MaxN 100009

struct muchie{
	int x;
	muchie *urm;
};

muchie *suc[MaxN],*pred[MaxN],*sol[MaxN],*aux;

int n,m,c[MaxN],uz[MaxN],nr,i,x,y,N;
//int *suc[MaxN],*pred[MaxN],*sol[MaxN];

void add_suc(int x,int y)
{
	muchie *aux=new muchie;
	aux->x=y; aux->urm=suc[x]; suc[x]=aux;
}

void add_pred(int x,int y)
{
	muchie *aux=new muchie;
	aux->x=x; aux->urm=pred[y]; pred[y]=aux;
}

void dfs(int nod)
{
	muchie *aux=new muchie;
	uz[nod]=1;
	
	aux=suc[nod];
	while(aux)
	{
		if(!uz[aux->x])
			dfs(aux->x);
		aux=aux->urm;
	}
	c[++N]=nod;
}

void df(int nod,int nr)
{
	uz[nod]=1;
	muchie *aux=new muchie;
	aux->x=nod; aux->urm=sol[nr];
	sol[nr]=aux;
	
	aux=pred[nod];
	while(aux)
	{
		if(!uz[aux->x])
			df(aux->x,nr);
		aux=aux->urm;
	}
}

int main()
{
	freopen("ctc.in","r",stdin);
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;i++)
	{
		scanf("%d%d",&x,&y);
		add_suc(x,y);
		add_pred(x,y);
	}
	
	for(i=1;i<=n;i++)
		if(!uz[i])
			dfs(i);
		
	memset(uz,0,sizeof(uz));
	
	for(i=N;i>=1;i--)
		if(!uz[c[i]])
			nr++, df(c[i],nr);
		
	freopen("ctc.out","w",stdout);
	printf("%d\n",nr);
	for(i=1;i<=nr;i++)
	{
		aux=sol[i];
		while(aux)
		{
			printf("%d ",aux->x);
			aux=aux->urm;
		}
		printf("\n");
	}
	return 0;
}