Cod sursa(job #592339)

Utilizator mathboyDragos-Alin Rotaru mathboy Data 27 mai 2011 21:18:17
Problema Componente biconexe Scor 58
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 kb
#include <cstdio>
#include <vector>
#include <stack>

#define MAXN 100010
using namespace std;

vector <int> G[MAXN];
int dfn[MAXN], low[MAXN], n, m;
stack <pair <int, int> > stk;
vector <int> V[MAXN];
int sol, cx, cy;
void solve(int x, int y)
{
	sol += 1;
	V[sol].push_back(stk.top().second);
	do {
		cx = stk.top().first;
		cy = stk.top().second;
		stk.pop();
		
		V[sol].push_back(cx);
	} while(cx != x && cy != y);
}
void DF(int node, int f, int tm)
{
	dfn[node] = tm;
	low[node] = dfn[node];
	for (vector <int> :: iterator it = G[node].begin(); it != G[node].end(); it++) {
		
		if (*it == f) continue;
		if (dfn[*it] == -1) {
			stk.push(make_pair(node, *it));
			DF(*it, node, tm + 1);
			
			low[node] = min(low[node], low[*it]);
			if (low[*it] >= dfn[node])
					solve(node, *it); // am gasit punct de articulatie
		}
		else low[node] = min(low[node], dfn[*it]);
	}
}
int main () {
	
	freopen ("biconex.in", "r", stdin);
	freopen ("biconex.out", "w", stdout);
	
	int a, b, i;
	scanf ("%d %d", &n, &m);
	
	for (; m--; ) {
		
		scanf("%d%d\n", &a, &b);
		G[a].push_back(b);
		G[b].push_back(a);
	}
	
	for (i = 1; i <= n; i++)
		dfn[i] = -1;
	
	DF(1, 0, 0);
	printf ("%d\n", sol);
	for (i = 1; i <= sol; i++) {
		for (int j = 0; j < V[i].size(); j++)
			printf("%d ", V[i][j]);
		printf ("\n");
	}
	return 0;
}