Cod sursa(job #255417)

Utilizator cameleonGeorgescu Dan cameleon Data 9 februarie 2009 18:04:48
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include<fstream.h>
#define fis1 "ctc.in"
#define fis2 "ctc.out"
#define nmax 100001
#define mmax 200001
ifstream f(fis1);
ofstream g(fis2);
struct lista
{
long inf;lista *urm;}*a[nmax],*at[nmax],*c[nmax];
long n,m,v[nmax],nr,t[nmax],k;

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

}
f.close();
}
void timp(long x)
{
v[x]=1;
for(lista *p=a[x];p;p=p->urm)
	if(v[p->inf]==0)
	{timp(p->inf);
	}
 t[++k]=x;
}
void df2(long x,long nr)
{
v[x]=0;  lista *q=new lista;
		q->inf=x;q->urm=c[nr];c[nr]=q;
for(lista *p=at[x];p;p=p->urm)
	if(v[p->inf]==1)df2(p->inf,nr);
}
void write()
{
g<<nr<<'\n';
for(long i=1;i<=nr;i++)
	{
	for(lista *p=c[i];p;p=p->urm)
		g<<p->inf<<' ';
	g<<'\n';

	}
g.close();

}
int main()
{
read();
long i;
for(i=1;i<=n;i++)
	if(!v[i])timp(i);
for(i=n;i;--i)
if(v[t[i]])
	{++nr;
	df2(t[i],nr);
	}

write();

return 0;

}