Cod sursa(job #255884)

Utilizator diannaDiaconu Diana dianna Data 10 februarie 2009 20:34:54
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include<fstream.h>
ifstream f("ctc.in");
ofstream g("ctc.out");
const int Nmax=100010;
long n,m,nr;
struct elem
{	int inf;
	elem *urm;
}*a[Nmax],*at[Nmax],*sol[Nmax];
int viz[Nmax],d[Nmax];

void citire()
{
 int x,y;
 f>>n>>m;
 for(int 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 conex(elem *a[],int i)
{
 viz[i]=1;
 d[i]++;
 elem *q;
 int c[100];
 c[0]=i;
 int p=0,u=1;
 while(p<u)
 {
	 q=a[c[p]];
	 while(q)
	 {
		if(viz[q->inf]==0)
		{
			d[q->inf]++;
			c[u++]=q->inf;
			viz[q->inf]=1;
		}
		q=q->urm;
	 }
	 p++;
 }
}

void solutie()
{
 nr++;
 for(int i=1;i<=n;i++)
	if(d[i]==2)
	{
		elem *p=new elem;
		p->inf=i;
		p->urm=sol[nr];
		sol[nr]=p;
		d[i]=-1;
	}
	else
		d[i]=0;
}

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

void init()
{
 for(int i=0;i<=n;i++)
	viz[i]=0;
}

void main()
{
 citire();
 for(int i=1;i<=n;i++)
 {
	if(d[i]!=-1)
	{
		init();
		conex(a,i);
		init();
		conex(at,i);
		solutie();
	}
 }
 afisare();
 g.close();
}