Cod sursa(job #431422)

Utilizator bixcabc abc bixc Data 31 martie 2010 23:20:38
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.55 kb
#include <cstdio>
#include <vector>
#include <list>
#include <stack>
using namespace std;

#define Nmax 100010
#define Mmax 200010

int n, m, nr_comp;
int Niv[Nmax], low[Nmax];
vector <int> V[Nmax];
list <int> Sol[Mmax];
stack <int> S;

void citire () {

	int i, x, y;
	
	scanf ("%d %d", &n, &m);
	for (i = 1; i <= m; i++) {
		scanf ("%d %d", &x, &y);
		V[x].push_back (y);
		V[y].push_back (x);
	}
}

void biconex (int x, int y) {
	
	int xx, yy;
	do {
		yy = S.top (); S.pop ();
		xx = S.top (); S.pop ();
		
		Sol[nr_comp].push_front (yy);
		//Sol[nr_comp].push_front (xx);
	} while (x != xx || y != yy);
	Sol[nr_comp].push_front (xx);
}

void dfs (int nod, int niv, int tata) {
	
	Niv[nod] = low[nod] = niv;
	for (vector <int>::iterator it = V[nod].begin (); it != V[nod].end (); it++) 
		if (*it != tata) {
			if ( !Niv [*it] ) {
				S.push (nod); S.push (*it);
				
				dfs (*it, niv + 1, nod);
				if (low[*it] < low[nod]) low[nod] = low[*it];
				
				if (low[*it] >= niv)
					nr_comp++, biconex (nod, *it);
			}
			
			else 
				if (Niv[*it] < low[nod]) low[nod] = Niv[*it];
		}
}

void afisare () {
	
	printf ("%d\n", nr_comp);
	for (int i = 1; i <= nr_comp; i++) {
		for (list <int>::iterator it = Sol[i].begin (); it != Sol[i].end (); it++)
			printf ("%d ", *it);
		printf ("\n");
	}
}

int main () {

	freopen ("biconex.in", "r", stdin);
	freopen ("biconex.out", "w", stdout);

	citire ();
	
	int i;
	for (i = 1; i <= n; i++)
		if (!Niv[i]) dfs (i, 1, 0);
	
	afisare ();
	
	return 0;
}