Cod sursa(job #281166)

Utilizator cotofanaCotofana Cristian cotofana Data 13 martie 2009 21:01:37
Problema Componente tare conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb
#include <stdio.h>
#define dim 100100

struct nod
{
	int nr;
	nod *urm;
};
int n, m, plus[dim], minus[dim], ct, fol[dim];
nod *g[dim], *gt[dim];

void add(nod *&p, int nr)
{
	nod *n1=new nod;
	n1->nr=nr;
	n1->urm=p;
	p=n1;
}

void dfp(int x)
{
	nod *n1;
	plus[x]=1;
	n1=g[x];
	while (n1)
	{
		if (!plus[n1->nr]) dfp(n1->nr);
		n1=n1->urm;
	}
}

void dfm(int x)
{
	nod *n1;
	minus[x]=1;
	n1=gt[x];
	while (n1)
	{
		if (!minus[n1->nr]) dfm(n1->nr);
		n1=n1->urm;
	}
}

void conex()
{
	int i, j;
	ct=1;
	for (i=1; i<=n; i++)
	{
		if (!fol[i])
		{
			dfp(i);
			dfm(i);
			for (j=i; j<=n; j++)
			{
				if (plus[j]*minus[j])				
					fol[j]=ct;
				plus[j]=minus[j]=0;
			}
			ct++;
		}
	}
}

int main()
{
	int a, b;
	freopen("ctc.in", "r", stdin);
	freopen("ctc.out", "w", stdout);
	scanf("%d %d\n", &n, &m);
	for (; m; m--)
	{
		scanf("%d %d\n", &a, &b);
		add(g[a], b);
		add(gt[b], a);
	}
	conex();
	printf("%d\n", --ct);
	for (; ct; ct--)
	{
		for (int i=1; i<=n; i++) 
			if (fol[i]==ct) printf("%d ", i);
		printf("\n");
	}
	return 0;
}