Cod sursa(job #390651)

Utilizator ionutz32Ilie Ionut ionutz32 Data 4 februarie 2010 11:47:26
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include <stdio.h>
struct node
{
	int nr;
	node *adr;
};
int n,m,i,a,b,s[100005],nrc,min[100005],st[100005],ns,sol;
node *v[100005],*u,*comp[100005];
void tarjan(int nod)
{
	node *u;
	int d;
	s[nod]=1;
	st[++ns]=nod;
	d=++nrc;
	min[nod]=nrc;
	for (u=v[nod];u!=NULL;u=u->adr)
	{
		if (!s[u->nr])
		{
			tarjan(u->nr);
			if (min[u->nr]<min[nod])
				min[nod]=min[u->nr];
		}
		else
			if (s[u->nr]==1 && min[u->nr]<min[nod])
				min[nod]=min[u->nr];
	}
	if (min[nod]==d)
	{
		++sol;
		while (st[ns]!=nod)
		{
			u=new node;
			u->nr=st[ns];
			u->adr=comp[sol];
			comp[sol]=u;
			s[st[ns]]=2;
			--ns;
		}
		u=new node;
		u->nr=nod;
		u->adr=comp[sol];
		comp[sol]=u;
		s[nod]=2;
		--ns;
	}
}
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",&a,&b);
		u=new node;
		u->nr=b;
		u->adr=v[a];
		v[a]=u;
	}
	for (i=1;i<=n;++i)
		if (!s[i])
			tarjan(i);
	printf("%d\n",sol);
	for (i=1;i<=sol;++i)
	{
		for (u=comp[i];u!=NULL;u=u->adr)
			printf("%d ",u->nr);
		printf("\n");
	}
	return 0;
}