Cod sursa(job #838160)

Utilizator mathboyDragos-Alin Rotaru mathboy Data 19 decembrie 2012 00:34:17
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.61 kb
#include <cstdio>
#include <stack>
#include <vector>
#include <algorithm>
#include <cstring>
#include <string>

using namespace std;

const int maxn = 100010;
int nrc;
vector <int> g[maxn], c[maxn];
stack <pair <int, int > > ST;
int low[maxn], dfn[maxn];
int n;

void solve(int x, int y) {
	++nrc;
	int xx, yy;
	do {	
		xx = ST.top().first;
		yy = ST.top().second;
		c[nrc].push_back(xx); c[nrc].push_back(yy);
		ST.pop();
	} while(xx != x || yy != y);
}		
void dfs(int node, int f, int depth) {
	
	dfn[node] = low[node] = depth;	
	for(vector <int> :: iterator it = g[node].begin(); it != g[node].end(); ++it) {
		if(*it == f) continue;
		if(dfn[*it] == -1) {
			ST.push(make_pair(node, *it));
			dfs(*it, node, depth + 1);
			low[node] = min(low[node], low[*it]);

			if(low[*it] >= dfn[node]) {
//				printf("asdsadsadas\n");
				solve(node, *it);
			}
		}
		else low[node] = min(low[node], dfn[*it]);
	}
}
void print() {
	printf("%d\n", nrc);
	for(int i = 1; i <= nrc; ++i) {
		sort(c[i].begin(), c[i].end());
		c[i].erase(unique(c[i].begin(), c[i].end()) , c[i].end());
	}
	for(int i = 1; i <= nrc; ++i) {
		for(vector <int> :: iterator it = c[i].begin(); it != c[i].end(); ++it)
			printf("%d ", *it);
		printf("\n");
	}
}
int main() {
	freopen("biconex.in", "r", stdin);
	freopen("biconex.out", "w", stdout);
	
	int m, x, y;
	for( scanf("%d %d\n", &n, &m); m--; ) {
		scanf("%d %d\n", &x, &y);
		g[x].push_back(y);
		g[y].push_back(x);
	}
	memset(dfn, -1, sizeof(dfn));
	dfs(1, 0, 1);
/*
	for(int i = 1; i <= n; ++i)
		printf("%d ", low[i]);
	printf("\n");
	for(int i = 1;i <= n; ++i)
		printf("%d ", dfn[i]);
*/	print();
	return 0;
}