Cod sursa(job #478855)

Utilizator Addy.Adrian Draghici Addy. Data 20 august 2010 18:18:07
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.66 kb
#include <cstdio>
#include <algorithm>
#include <vector>
#include <set>

using namespace std;

#define NMAX 100050

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

int niv[NMAX], low[NMAX], viz[NMAX], T[NMAX], n, m, nivel, N, nr_sol;
vector <int> G[NMAX];
set <int> sol[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 i, x, y;
	
	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 componenta (int nod, int fiu) {
	
	int x, y;
	
	nr_sol++;
	
	do {
		x = S[N].x, y = S[N].y, N--;
		sol[nr_sol].insert (x);
		sol[nr_sol].insert (y);
	} while (x != nod && y != fiu);
}

void DFS (int nod) {
	
	int i, fiu;
	
	viz[nod] = 1;
	
	nivel++;
	niv[nod] = low[nod] = nivel;
	
	for (i = 0; i < (int) G[nod].size(); i++) {
		fiu = G[nod][i];
		if (fiu != T[nod])
			if (!viz[fiu]) {
				T[fiu] = nod;
				N++, S[N].x = nod, S[N].y = fiu;
				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 () {
	
	int i;
	
	for (i = 1; i <= n; i++)
		if (!viz[i])
			DFS (i);
}

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