Cod sursa(job #555560)

Utilizator cnt_tstcont teste cnt_tst Data 15 martie 2011 16:48:07
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.57 kb
#include <cstdio>
#include <list>

using namespace std;

#define NMAX 100050

struct muchie {
	int x, y;
} S[NMAX];

int T[NMAX], niv[NMAX], low[NMAX], N, nivel, sol, n;
list <int> G[NMAX], B[NMAX];

void citire (), biconex (), DFS (int), componenta (int, int), afisare ();

int main () {
	
	citire ();
	
	biconex ();
	
	afisare ();
	
	return 0;
}

void citire () {
	
	freopen ("biconex.in", "r", stdin);
	
	int m, i, x, y;
	
	scanf ("%d %d\n", &n, &m);
	
	for (i = 1; i <= m; i++) {
		scanf ("%d %d", &x, &y);
		G[x].push_back (y);
		G[y].push_back (x);
	}
}

void componenta (int x, int y) {
	
	int i, j;
	
	sol++;
	
	do {
		i = S[N].x, j = S[N].y, N--;
		B[sol].push_back (j);
	} while (i != x && j != y);
	
	B[sol].push_back (x);
}

void DFS (int nod) {
	
	int fiu;
	list <int>::iterator it;
	
	nivel++;
	niv[nod] = low[nod] = nivel;
	
	for (it = G[nod].begin (); it != G[nod].end (); it++) {
		fiu = *it;
		if (*it != T[nod]) {
			if (!niv[fiu]) {
				
				N++, S[N].x = nod, S[N].y = fiu;
				T[fiu] = nod; DFS (fiu);
				
				if (low[fiu] >= niv[nod]) componenta (nod, fiu);
				
				low[nod] = min (low[nod], low[fiu]);
			}
			else
				low[nod] = min (low[nod], niv[fiu]);
		}
	}
}

void biconex () {
	
	for (int i = 1; i <= n; i++)
		if (!niv[i]) DFS (i);
}

void afisare () {
	
	freopen ("biconex.out", "w", stdout);
	
	printf ("%d\n", sol);
	
	for (int i = 1; i <= sol; i++) {
		for (list <int>::iterator it = B[i].begin (); it != B[i].end (); it++)
			printf ("%d ", *it);
		printf ("\n");
	}
}