Cod sursa(job #501055)

Utilizator skullLepadat Mihai-Alexandru skull Data 14 noiembrie 2010 11:22:53
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.38 kb
#include <stdio.h>
#include <vector>
#include <stack>
using namespace std;
#define nmax 100005
#define mmax 200005
#define punct pair<int,int>
#define ff first
#define ss second

int n, nrsol;
stack<punct> st;
vector<int> G[nmax], solutii[nmax];
int lvl[nmax], c[nmax], viz[nmax];

void citire ()
{
	int i, m, x, y;
	freopen("biconex.in","r",stdin);
	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);
	}
}

void add (int x, int y)
{
	nrsol ++;
	punct varf;
	do{
		varf = st.top (); st.pop ();
		solutii[nrsol].push_back(varf.ss);
	}while (varf.ff!=x && varf.ss!=y);
	solutii[nrsol].push_back(varf.ff);
}

void dfs(int nod, int tata)
{
	int i, x;
	viz[nod] = 1; lvl[nod] = lvl[tata]+1; c[nod] = lvl[nod];
	for (i = 0; i < G[nod].size(); ++i)
	{
		x = G[nod][i];
		if ( !viz[x] )
		{
			st.push( make_pair(nod, x) );
			dfs(x, nod);
			if (c[x] < c[nod]) c[nod] = c[x];
			if (c[x] >= lvl[nod]) 
				add(nod, x);
		}
		else
			if (x != tata && c[x]<c[nod]) c[nod] = c[x];
	}
}

void afisare ()
{
	int i, j;
	freopen("biconex.out","w",stdout);
	printf("%d\n", nrsol);
	for (i = 1; i <= nrsol; ++i)
	{
		for (j = 0; j < solutii[i].size (); ++j)
			printf("%d ", solutii[i][j]);
		printf("\n");
	}
}

int main ()
{
	citire ();
	dfs (1,0);
	afisare ();
	return 0;
}