Cod sursa(job #353138)

Utilizator IoannaPandele Ioana Ioanna Data 4 octombrie 2009 12:01:58
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#include<stdio.h>
#define nmax 100010
long n,m,nr;
long s[nmax],v[nmax];

struct nod
{
	long info;
	nod *urm;
};

nod *g[nmax],*t[nmax],*c[nmax];

void InsertBegin(long a,long b)
{
	nod *aux;
	aux=new nod;
	aux->info=b;
	aux->urm=g[a];
	g[a]=aux;
	aux=new nod;
	aux->info=a;
	aux->urm=t[b];
	t[b]=aux;
}

void read()
{
	long i,a,b;
	scanf("%ld%ld",&n,&m);
	for (i=1;i<=m;i++)
	{
		scanf("%ld%ld",&a,&b);
		InsertBegin(a,b);
	}
}

void dfs(long i)
{
	nod *p;
	v[i]=1;
	for (p=g[i];p;p=p->urm)
	{
		if (!v[p->info])
		{
			dfs(p->info);
			s[++s[0]]=p->info;
		}
	}
}
	
void dfst(long i)
{
	nod *p,*aux;
	v[i]=0;
	aux=new nod;
	aux->info=i;
	aux->urm=c[nr];
	c[nr]=aux;
	for (p=t[i];p;p=p->urm)
	{
		if (v[p->info])
		{
			dfst(p->info);
		}
	}
}

void print()
{
	printf("%ld\n",nr);
	long i;
	nod *p;
	for (i=1;i<=nr;i++)
	{
		for (p=c[i];p;p=p->urm)
			printf("%ld ",p->info);
		printf("\n");
	}
}

int main()
{
	freopen("ctc.in","r",stdin);
	freopen("ctc.out","w",stdout);
	read();
	long i;
	for (i=1;i<=n;i++)
	{
		if (!v[i])
		{
			dfs(i);
			s[++s[0]]=i;
		}
	}
	for (i=n;i>=1;i--)
	{
		if (v[s[i]])
		{
			nr++;
			dfst(s[i]);
		}
	}
	print();
	return 0;
}