Cod sursa(job #278866)

Utilizator gabitzish1Gabriel Bitis gabitzish1 Data 12 martie 2009 16:13:17
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include <stdio.h>

int N, M, nr, cnt;
int viz[100005], st[100005];

typedef struct pnod
{
	int x;
	pnod *a;
} *pNod;
pNod g[100006], gt[100005], comp[100005];

void DF(int nod)
{
	viz[nod] = 1;
	pNod q;
	for (q = g[nod]; q != NULL; q = q -> a)
		if (!viz[q -> x]) DF(q -> x);
	st[++nr] = nod;
}

void DF2(int nod)
{
	viz[nod] = 2;
	pNod q;

	q = new pnod; q -> x = nod; q -> a = comp[cnt]; comp[cnt] = q;

	for (q = gt[nod]; q != NULL; q = q -> a)
		if (viz[q -> x] != 2) DF2(q -> x);
}


int main()
{
	freopen("ctc.in","r",stdin);
	freopen("ctc.out","w",stdout);

	int i, x, y;
	pNod q;

	scanf("%d %d",&N,&M);

	for (i = 1; i <= M; i++)
	{
		scanf("%d %d", &x, &y);
		q = new pnod; q -> x = y; q -> a = g[x]; g[x] = q;
		q = new pnod; q -> x = x; q -> a = gt[y]; gt[y] = q;
	}

	for (i = 1; i <= N; i++)
		if (!viz[i]) DF(i);

	for (i = N; i >= 1; i--)
		if (viz[st[i]] != 2) 
		{
			cnt++;
			DF2(st[i]);
		}

	printf("%d\n", cnt);
	for (i = 1; i <= cnt; i++)
	{
		for (q = comp[i]; q != NULL; q = q -> a) printf("%d ",q -> x);
		printf("\n");
	}
	return 0;
}