Cod sursa(job #499517)

Utilizator vlad_DVlad Dumitriu vlad_D Data 10 noiembrie 2010 07:07:17
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.47 kb
#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
#define pb(a) push_back(a)

int N; // numarul de noduri
vector<vector<int> > G; // graful
stack<pair<int, int> > st; //stackul de muchii
vector<int> dep, low; // depth and low level
vector<vector<int> > B; // biconexele
void biconex(int x, int y) {
	vector<int> c;
	int nx, ny;
	int lst = -1;
	do {
		nx = st.top().first; ny = st.top().second;
		st.pop();
		c.pb(ny);
		c.pb(nx);
	} while (nx != x || ny != y);
	sort(c.begin(), c.end());
	c = vector<int>(c.begin(), unique(c.begin(), c.end()));
	B.pb(c);
}
void dfs(int nod, int parent, int level) {
	dep[nod] = low[nod] = level;
	for (int i = 0; i < G[nod].size(); ++i) {
		int nod2 = G[nod][i];
		if (nod2 == parent) continue;
		//viziteaza
		if (dep[nod2] == -1) {
			// pune muchia in stack
			st.push(make_pair(nod, nod2));
			dfs(nod2, nod, level + 1);
			low[nod] = min(low[nod], low[nod2]);
			if (low[nod2] >= dep[nod]) biconex(nod, nod2);
		} else low[nod] = min(low[nod], low[nod2]);
	}
}
int main() {
	freopen("biconex.in", "r", stdin);
	freopen("biconex.out", "w", stdout);
	int M;
	scanf("%d %d", &N, &M);
	G.resize(N+1);
	while (M--) {
		int a, b;
		scanf("%d %d", &a, &b);
		G[a].pb(b);
		G[b].pb(a);
	}
	dep.assign(N+1, -1);
	low.assign(N+1, -1);
	dfs(1, 0, 0); //level, parent
	printf("%d\n", B.size());
	for (int i = 0; i < B.size(); ++i) {
		for (int j = 0; j < B[i].size(); ++j) 
			printf("%d ", B[i][j]);
		printf("\n");
	}
	return 0;
}