Cod sursa(job #267047)

Utilizator ZillaMathe Bogdan Zilla Data 26 februarie 2009 17:46:19
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.68 kb
#include <stdio.h>

#define Nmax 200100

struct nod{
	int info;
	nod *next;
};

nod *p[Nmax];
nod *pt[Nmax];

int n,m,nr,viz[Nmax],postordine[Nmax],rev[Nmax],com;

void adauga(int j, int k)
{
	nod *elem=new nod;
	elem->info=k;
	elem->next=p[j];
	p[j]=elem;
}

void adaugat(int j, int k)
{
	nod *elem=new nod;
	elem->info=k;
	elem->next=pt[j];
	pt[j]=elem;
}

void DFS(int i)
{
	nod *current=p[i];
	viz[i]=1;
	while(current!=NULL)
		{
			if(viz[current->info]==0)
				DFS(current->info);
			current=current->next;
		}
	postordine[++nr]=i;
}

void DFST(int i)
{
	nod *current=pt[i];
	viz[i]=0;
//	printf("%d ",i);
	adauga(n+com,i);
	while(current!=NULL)
		{
			if(viz[current->info]!=0)
				DFST(current->info);
			current=current->next;
		}
}

void revizit(int i)
{
	nod *current=pt[i];
	rev[i]=1;
	while(current!=NULL)
		{
			if(rev[current->info]==0)
				revizit(current->info);
			current=current->next;
		}
}

void afis(int i)
{
	nod *current=p[i];
	while(current)
		{
			printf("%d ",current->info);
			current=current->next;
		}
}

int main()
{
	int i,x,y;
	freopen("ctc.in","r",stdin);
	freopen("ctc.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;++i)
		{
			scanf("%d%d",&x,&y);
			adauga(x,y);
			adaugat(y,x);
		}

	for(i=1;i<=n;++i)
		{
			if(viz[i]==0)
				DFS(i);
		}
 /*	for(i=n;i>0;--i)
		if(rev[postordine[i]]==0)
			{
				++com;
				revizit(i);
			}       */

	for(i=n;i>0;--i)
		if(viz[postordine[i]]!=0)
			{
				++com;
				DFST(postordine[i]);
			}
	printf("%d\n",com);
	for(i=1;i<=com;++i,printf("\n"))
		for(nod *it=p[n+i];it;it=it->next)
			printf("%d ",it->info);
	return 0;
}