Cod sursa(job #255945)

Utilizator Andrei_ScorpioAndreiana Andrei Daniel Andrei_Scorpio Data 10 februarie 2009 21:31:59
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb
#include<fstream.h>
#define Nmax 100
ifstream f("ctc.in");
ofstream g("ctc.out");
long n,m,k,nr,t[Nmax],viz[Nmax];
struct elem
{	long inf;
	elem *urm;
}*a[Nmax],*at[Nmax],*sol[Nmax];

void citire()
{
 long x,y;
 f>>n>>m;
 for(long i=0;i<m;i++)
 {
	f>>x>>y;
	elem *p=new elem;
	p->inf=y;
	p->urm=a[x];
	a[x]=p;
	p=new elem;
	p->inf=x;
	p->urm=at[y];
	at[y]=p;
 }
}

void parcurg_1(long x)
{
 for(elem *p=a[x];p;p=p->urm)
	if(viz[p->inf]==0)
	{
		viz[p->inf]=1;
		parcurg_1(p->inf);
	}
 k++;
 t[k]=x;
}

void parcurg_2(long x,long nr)
{
	elem *q=new elem;
	q->inf=x;
	q->urm=sol[nr];
	sol[nr]=q;
	viz[x]=-1;
	for(elem *p=at[x];p;p=p->urm)
	if(viz[p->inf]==1)
	{

		parcurg_2(p->inf,nr);
	}
}

void afisare()
{
 g<<nr<<'\n';
 for(long i=1;i<=nr;i++)
 {
	while(sol[i])
	{
		g<<sol[i]->inf<<" ";
		sol[i]=sol[i]->urm;
	}
	g<<'\n';
 }
}

int main()
{
 citire();
 for(long i=1;i<=n;i++)
	if(!viz[i])
	{       viz[i]=1;
		parcurg_1(i);
	}
 for(i=n;i>=1;i--)
	if(viz[t[i]]==1)
	{
		nr++;
		parcurg_2(t[i],nr);
	}
 afisare();
 g.close();
 return 0;
}