Cod sursa(job #392535)

Utilizator AndreiDDiaconeasa Andrei AndreiD Data 7 februarie 2010 17:59:17
Problema Componente biconexe Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.81 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,frecv[Nmax];
char s[1000];

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);
		//printf("%d %d\n", x,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", &n, &m);
	
	for (i=1;i<=m;++i)
	{
		//scanf("%d %d", &x, &y);
		x=y=0;
		
		gets(s);
		j=0;
		
		while(s[j]>='0' && s[j]<='9')
		{
			x=x*10+s[j]-'0';
			j++;
		}
		j++;
		while(s[j]>='0' && s[j]<='9')
		{
			y=y*10+s[j]-'0';
			j++;
		}
		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)
	{
		int mm=0;
		for (j=0;j<sol[i].size();++j)
		{
			x=sol[i][j];
			frecv[x]++;
			if (x>mm) mm=x;
		}
		//printf("%d ", sol[i][j]);
		for (j=1;j<=mm;++j)
			 if (frecv[j]!=0){
				 printf("%d ",j);
				 frecv[j]=0;
			 }
		printf("\n");
	}
		
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
	
}