Cod sursa(job #280136)

Utilizator mircea_infoSuciu Mircea-Gabriel mircea_info Data 13 martie 2009 11:06:46
Problema Componente biconexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.49 kb
//componente biconexe bc

#include <stdio.h>
#define nmax 100001

struct nod {int inf; nod *urm;} *g[nmax],*sol[nmax];
int n,m,st[4*nmax],vf,nr,nrsol;
int low[nmax],tata[nmax],viz[nmax],niv[nmax];

int min(int x, int y)
{
	return x<y?x:y;
}

void baga(int x, int y)
{
	nod *q=new nod;
	q->inf=y;
	q->urm=g[x];
	g[x]=q;
	q=new nod;
	q->inf=x;
	q->urm=g[y];
	g[y]=q;
}

void update(int x, int y)
{
	nrsol++;
	int z1,z2;
	do
	{
		z1=st[vf];
		z2=st[vf-1];
		nod *q=new nod;
		q->inf=z1;
		q->urm=sol[nrsol];
		sol[nrsol]=q;
		q=new nod;
		q->inf=z2;
		q->urm=sol[nrsol];
		sol[nrsol]=q;
		vf-=2;
	}
	while(z1-y || z2-x);

}

void parc(int x)
{
	viz[x]=1;
	low[x]=niv[x]=nr++;
	for(nod *q=g[x];q;q=q->urm)
		if(!viz[q->inf])
		{
			tata[q->inf]=x;
			st[++vf]=x;
			st[++vf]=q->inf;
			parc(q->inf);
			if(low[q->inf]>=niv[x])
				update(x,q->inf);
			low[x]=min(low[x],low[q->inf]);
		}
		else
			low[x]=min(low[x],niv[q->inf]);
}

int main()
{
	int i,x,y;
	freopen("biconex.in","r",stdin);
	freopen("biconex.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;i++)
	{
		scanf("%d%d",&x,&y);
		baga(x,y);
	}
	for(i=1;i<=m;i++)
		if(!viz[i])
		{
			nr=1;
			parc(i);
		}
	printf("%d\n",nrsol);
	for(i=1;i<=nrsol;i++)
	{
		for(nod *q=sol[i];q;q=q->urm)
			viz[q->inf]=0;
		for(q=sol[i];q;q=q->urm)
			if(!viz[q->inf])
			{
				printf("%d ",q->inf);
				viz[q->inf]=1;
			}
        printf("\n");
	}
	fclose(stdout);
	return 0;
}