Cod sursa(job #727559)

Utilizator Addy.Adrian Draghici Addy. Data 28 martie 2012 08:45:18
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.5 kb
#include <cstdio>
#include <set>
#include <stack>
#include <vector>
#include <algorithm>

using namespace std;

#define NMAX 200050

int LEV[NMAX], LOW[NMAX], T[NMAX], N, M, K, IDX;
vector <int> G[NMAX];
stack < pair <int, int> > S;
set <int> C[NMAX];

void component (int, int), dfs (int), input (), output ();

int main () {
	
	input ();
	
	dfs (1);
	
	output ();
	
	return 0;
}

void dfs (int node) {
	
	int son;
	vector <int>::iterator it;
	
	LEV[node] = LOW[node] = ++IDX;
	for (it = G[node].begin (); it != G[node].end (); it++) {
		son = *it;
		
		if (son != T[node]) {
			if (!LEV[son]) {
				S.push (make_pair (node, son));
				T[son] = node; dfs (son);
				
				LOW[node] = min (LOW[node], LOW[son]);
				if (LOW[son] >= LEV[node]) component (node, son);
			}
			else
				LOW[node] = min (LOW[node], LEV[son]);
		}
	}
	
}

void component (int x, int y) {
	
	K++; int a, b;
	do {
		a = S.top ().first; b = S.top ().second; S.pop ();
		C[K].insert (a); C[K].insert (b);
	}
	while (a != x && b != y);
}

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

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