Cod sursa(job #408418)

Utilizator za_wolfpalianos cristian za_wolf Data 3 martie 2010 00:40:02
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.41 kb
#include<stdio.h>
#include<string.h>
#define NMAX 100100
#define MMAX 200100
int *g[2][NMAX],vviz[NMAX],y[NMAX],*sol[NMAX],w[NMAX],d[NMAX],z[NMAX],i,j,n,m,k,l,a,s,rez,nod;
void df(int k)
{
	for (int i=1;i<=g[a][k][0];i++)
	{
		nod=g[a][k][i];
		if (!z[nod])
		{
			z[nod]=1;
			d[nod]++;
			df(nod);
		}
	}
}
int main()
{
	struct kkt
	{
		int X,Y;
	};
	kkt x[MMAX];
	freopen("ctc.in","r",stdin);
	freopen("ctc.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (i=1;i<=m;i++)
	{
		scanf("%d%d",&x[i].X,&x[i].Y);
		y[x[i].X]++;
		z[x[i].X]++;
	}

	for (i=1;i<=n;i++)
	{
		g[0][i] = new int [y[i]+5];
		g[1][i] = new int [z[i]+5];
		y[i]=z[i]=g[0][i][0]=g[1][i][0]=0;
	}

	for (i=1;i<=m;i++)
	{
		g[0][x[i].X][++g[0][x[i].X][0]]=x[i].Y;
		g[1][x[i].Y][++g[1][x[i].Y][0]]=x[i].X;
	}

	for (i=1;i<=n;i++)
		if (!vviz[i])
		{
			a=0;
			for (j=0;j<=n;j++)
				z[j]=y[j]=d[j]=0;
			z[i]=1;
			df(i);
			a=1;
			for (j=0;j<=n;j++)
				z[j]=0;
			z[i]=1;
			df(i);
			rez++;
			d[i]=2;
			for (j=1;j<=n;j++)
				if (d[j]==2)
					y[++y[0]]=j;
			sol[rez] = new int [y[0]+5];
			sol[rez][0]=y[0];
			for (j=1;j<=y[0];j++)
			{
				sol[rez][j]=y[j];
				vviz[y[j]]=1;
			}
			for (j=1;j<=n;j++)
				if (d[j]==2)
					vviz[y[j]]=1;

		}

	printf("%d\n",rez);
	for (i=1;i<=rez;i++)
	{
		for (j=1;j<=sol[i][0];j++)
			printf("%d ",sol[i][j]);
		printf("\n");
	}

	return 0;
}