Cod sursa(job #392524)

Utilizator AndreiDDiaconeasa Andrei AndreiD Data 7 februarie 2010 17:33:34
Problema Componente biconexe Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

#define file_in "biconex.in"
#define file_out "biconex.out"

#define Nmax 213213

vector<int> G[Nmax],sol[Nmax];
int n,m;
struct bc
{
	int f,t;
}
st[Nmax];
int nrb,vfst;
int d[Nmax],l[Nmax],nr;

void baga(int a, int b)
{
	int x,y;
	nrb++;
	do
	{
		x=st[vfst].f;
		y=st[vfst].t;
		vfst--;
		sol[nrb].push_back(y);
	}
	while(x!=a || y!=b);
	sol[nrb].push_back(x); 
}
		
	

void biconex(int nod, int tnod)
{
	nr++;
	d[nod]=l[nod]=nr;
	
	for (int i=0;i<G[nod].size();++i)
	{
		int x=G[nod][i];
		
		if (x!=tnod && d[x]<d[nod])
		{
			vfst++;
			st[vfst].f=x;
			st[vfst].t=nod;
		}
		if (d[x]==-1)
		{
			biconex(x,nod);
			l[nod]=min(l[x],l[nod]);
			if (l[x]>=d[nod])
				baga(x,nod);
		}
		else
		if (x!=tnod)
			l[nod]=min(l[nod],d[x]);
	}
}


int main()
{
	int i,x,y,j;
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);
	
	scanf("%d %d", &n, &m);
	
	for (i=1;i<=m;++i)
	{
		scanf("%d %d", &x, &y);
		
		G[x].push_back(y);
		G[y].push_back(x);
	}
	
	
	//initializari
	for (i=1;i<=n;++i)
		 d[i]=l[i]=-1;
	st[0].f=1;
	st[0].t=-1;
	vfst=0;
	biconex(1,-1);
	
	printf("%d\n", nrb);
	for (i=1;i<=nrb;++i)
	{
		for (j=0;j<sol[i].size();++j)
			 printf("%d ", sol[i][j]);
		printf("\n");
	}
		
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
	
}