Cod sursa(job #263058)

Utilizator sory1806Sandu Sorina-Gabriela sory1806 Data 19 februarie 2009 21:26:00
Problema Componente tare conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.32 kb
#include<stdio.h>
#define max 100010
long s[max], x[max], n, m, nr;
int vza[max], vzt[max];
struct elem
{       long vf;
	elem *urm;
}	*ga[max], *gt[max], *q;
FILE *f, *g;

void read()
{       long i, x, y;
	f=fopen("ctc.in", "r");
	fscanf(f, "%ld%ld", &n, &m);
	for(i=1; i<=m; i++)
	{	fscanf(f, "%ld%ld", &x, &y);
		q=new elem;
		q->vf=y;
		q->urm=ga[x];
		ga[x]=q;
		q=new elem;
		q->vf=x;
		q->urm=gt[y];
		gt[y]=q;
	}
}

void empty()
{       long i;
	for(i=1; i<=n; i++)
	{       vza[i]=0; vzt[i]=0;
		if(x[i]==2)
			x[i]=nr;
		if(x[i]<0)
		{	vza[i]=1; vzt[i]=1;
		}
		if(x[i]>0)
			x[i]=0;
	}
}

void dfa(int z,int k)
{       elem *q;
	s[k]=z;
	vza[z]=1;
	x[z]++;
	q=ga[z];
	while(q)
	{       if(vza[q->vf]==0)
		{       dfa(q->vf, k+1);
		}
		q=q->urm;
	}
}

void dft(int z,int k)
{       elem *q;
	s[k]=z;
	vzt[z]=1;
	x[z]++;
	q=gt[z];
	while(q)
	{       if(vzt[q->vf]==0)
		{       dft(q->vf, k+1);
		}
		q=q->urm;
	}
}

int main()
{       long i, j;
	read();
	for(i=1; i<=n; i++)
	{       if(vza[i]==0)
		{	dfa(i, 1);
			dft(i, 1);
			nr--;
			empty();
		}
	}
	g=fopen("ctc.out", "w");
	fprintf(g, "%ld\n", nr*(-1));
	for(i=-1; i>=nr; i--)
	{	for(j=1; j<=n; j++)
			if(x[j]==i)
				fprintf(g, "%ld ", j);
		fprintf(g, "\n");
	}
	fclose(g);
	return 0;
}