Cod sursa(job #394829)

Utilizator GotenAmza Catalin Goten Data 11 februarie 2010 17:54:59
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include<stdio.h>

int ver[400100],leg[400100],start[100100],ac[100100],niv[100100],s[200100],sol[300100],k,q,c,pus[100100],l,S[200100];

void dfs(int nod, int pre)
{
	ac[nod]=niv[nod]=niv[pre]+1;
	pus[nod]=1;
	int t=start[nod];
	while(t)
	{
		if(ver[t]!=pre)
			if(!pus[ver[t]])
			{
				s[++l]=nod;
				S[l]=ver[t];
				dfs(ver[t],nod);
				if(ac[nod]>ac[ver[t]])
					ac[nod]=ac[ver[t]];
				if(ac[ver[t]]>=niv[nod])
				{
					c++;
					while(s[l]!=nod)
						sol[++k]=S[l--];
					sol[++k]=nod;
					sol[++k]=S[l--];
					sol[++k]=0;
				}
			}
			else
				if(ac[nod]>niv[ver[t]])
					ac[nod]=niv[ver[t]];
		t=leg[t];
	}
}

int main()
{
	int n,m,x,y;
	freopen("biconex.in","r",stdin);
	freopen("biconex.out","w",stdout);
	scanf("%d %d",&n,&m);
	while(m--)
	{
		scanf("%d %d",&x,&y);
		ver[++q]=y;
		leg[q]=start[x];
		start[x]=q;
		ver[++q]=x;
		leg[q]=start[y];
		start[y]=q;
	}
	dfs(1,0);
	m=1;
	printf("%d\n",c);
	while(m<=k)
	{
		while(sol[m])
			printf("%d ",sol[m++]);
		printf("\n");
		m++;
	}
}