Cod sursa(job #428991)

Utilizator jeanFMI - Petcu Ion Cristian jean Data 29 martie 2010 19:16:36
Problema Componente biconexe Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 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];

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

bool in_bcx[Nmax];

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

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;
}