Cod sursa(job #559868)

Utilizator skullLepadat Mihai-Alexandru skull Data 18 martie 2011 10:29:01
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 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, urm;
	viz[nod] = 1; lvl[nod] = lvl[tata] + 1; c[nod] = lvl[nod];
	for (i = 0; i < G[nod].size (); ++i)
	{
		urm = G[nod][i];
		if ( !viz[urm] )
		{
			st.push( make_pair(nod, urm) );
			dfs(urm, nod);
			if (c[urm] < c[nod]) c[nod] = c[urm];
			if (c[urm] >= lvl[nod])
				add(nod, urm);
		}
		else if (urm != tata && c[urm] < c[nod]) c[nod] = c[urm];
	}
}

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