Cod sursa(job #408383)

Utilizator za_wolfpalianos cristian za_wolf Data 2 martie 2010 23:59:32
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 kb
#include<stdio.h>
#include<string.h>
#define NMAX 101000
#define MMAX 201000
int *g[2][NMAX],vviz[NMAX],y[NMAX],*sol[NMAX],w[NMAX],viz[NMAX],d[NMAX],z[NMAX],i,j,n,m,k,l,a,s,rez,nod;
struct kkt
{
	int X,Y;
};
kkt x[MMAX];
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()
{
	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]+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])
		{
			memset(z,0,sizeof(z));
			memset(y,0,sizeof(y));
			memset(d,0,sizeof(d));
			a=0;
			memset(viz,0,sizeof(viz));
			viz[i]=1;
			df(i);
			a=1;
			memset(viz,0,sizeof(viz));
			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]+1];
			sol[rez][0]=y[0];
			for (j=1;j<=y[0];j++)
			{
				sol[rez][j]=y[j];
				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;
}