Cod sursa(job #255327)

Utilizator cameleonGeorgescu Dan cameleon Data 9 februarie 2009 10:07:02
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 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;
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 df1(long x)
{
v[x]=-1;
for(lista *p=a[x];p;p=p->urm)
	if(v[p->inf]==0)df1(p->inf);
}
void df2(long x,long nr)
{
v[x]=nr;  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();
}
/*void print(lista *a[])
{
for(long i=1;i<=n;i++)
	{
	for(lista* p=a[i];p;p=p->urm)
		cout<<p->inf<<" ";
	cout<<'\n';
	}
cout<<"***********\n";
} */
int main()
{
read();
/*print(a);print(at);*/
for(long i=1;i<=n;i++)
	{
	if(v[i]==0)
		{
		nr++;
		df1(i);
		df2(i,nr);
		for(long j=1;j<=n;j++)
			if(v[j]==-1)v[j]=0;
		}

	}
write();

return 0;

}