Cod sursa(job #408434)

Utilizator za_wolfpalianos cristian za_wolf Data 3 martie 2010 01:03:17
Problema Componente tare conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.44 kb
#include<stdio.h>
#include<string.h>
#define NMAX 100100
#define MMAX 200100
int *g[2][NMAX],y[NMAX],*sol[NMAX],w[NMAX],z[NMAX],i,j,n,m,k,l,a,s,rez,nod;
char null[NMAX],d[NMAX],vviz[NMAX],viz[NMAX];
void df(int k)
{
	for (int i=1;i<=g[a][k][0];++i)
	{
		nod=g[a][k][i];
		if (!viz[nod])
		{
			viz[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].Y]++;
	}

	for (i=1;i<=n;++i)
	{
		g[0][i] = new int [y[i]+2];
		g[1][i] = new int [z[i]+2];
		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)
				viz[j]=y[j]=d[j]=0;
			df(i);
			a=1;
			for (j=0;j<=n;++j)
				viz[j]=0;
			viz[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]+2];
			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;
}