Cod sursa(job #428996)

Utilizator jeanFMI - Petcu Ion Cristian jean Data 29 martie 2010 19:20:22
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
#include<stdio.h>
#include<stack>
#include<vector>
#define Nmax 100010
#define pb push_back
#define mp make_pair
using namespace std;

int niv[Nmax],low[Nmax],i,n,a,b,m,Cbcx,T[Nmax],bcx[Nmax];

vector<int> V[Nmax], Sol[Nmax];
stack < pair <int,int> > S;

void comp(int x, int y)
{
	int a,b,i;
	Cbcx++;
	
	do
	{
		a=S.top().first; 
		b=S.top().second;
		
		if(bcx[a]!=Cbcx) {Sol[Cbcx].pb(a); bcx[a]=Cbcx;}
		if(bcx[b]!=Cbcx) {Sol[Cbcx].pb(b); bcx[b]=Cbcx;}
		
		S.pop();
	}
	while(a!=x || b!=y);
}

void dfs (int nod, int nivel)
{
	int i,N=V[nod].size(),fiu;
	
	niv[nod]=low[nod]=nivel;
	
	for(i=0;i<N;i++)
	{
		fiu=V[nod][i];
		if(fiu==T[nod]) continue;
			
		if(!niv[fiu])
		{
			T[fiu]=nod;
			S.push(mp(nod,fiu));
			dfs(fiu,nivel+1);
			
			if(low[fiu]<low[nod]) low[nod]=low[fiu];
			if(low[fiu]>=niv[nod]) comp(nod,fiu);
		}
		else if(low[fiu]<low[nod]) low[nod]=low[fiu];
	}
}

int main()
{
	freopen("biconex.in","r",stdin);
	freopen("biconex.out","w",stdout);
	
	scanf("%d %d",&n,&m);
	
	for(i=1;i<=m;i++)
	{
		scanf("%d %d",&a,&b);
		V[a].pb(b);
		V[b].pb(a);
	}
	
	dfs(1,1);
	
	printf("%d\n",Cbcx);
	for(a=1;a<=Cbcx;a++)
	{
		b=Sol[a].size();
		for(i=0;i<b;i++)
			printf("%d ",Sol[a][i]);
		printf("\n");
	}
	return 0;
}