Cod sursa(job #718099)

Utilizator prisonbreakMichael Scofield prisonbreak Data 20 martie 2012 15:25:01
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.41 kb
#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>

const int maxn = 100005;

using namespace std;

stack <pair <int, int > > stk;
int dfn[maxn], low[maxn], comp;
vector <int> graph[maxn], v[maxn];

void write(int x, int y) {
	++comp; 
	int xs, ys;
	do {	
		
		xs = stk.top().first; 
		ys = stk.top().second; 
		stk.pop();
		v[comp].push_back(xs); v[comp].push_back(ys);
	}while(xs != x || ys != y);
}
void dfs(int node, int lev, int f){
	
	dfn[node] = low[node] = lev;
	
	for( vector <int> :: iterator it = graph[node].begin(); it != graph[node].end(); ++it ) {
		if(*it == f) continue;
		if(dfn[*it] == -1) {
			stk.push( make_pair(node, *it) ) ;
			dfs(*it, lev + 1, node); 
			low[node] = min(low[*it], low[node]);
			if(low[*it] >= dfn[node]) {
				write(node, *it);
			}
		}
		else low[node] = min(low[node], low[*it]);
	}

}
int main(){

	freopen("biconex.in", "r", stdin);
	freopen("biconex.out", "w", stdout);
	
	int n, m; 
	for( scanf("%d %d\n", &n, &m); m--; ) {
		int a, b;
		scanf("%d %d\n", &a, &b); 
		graph[a].push_back(b); graph[b].push_back(a);
	}
	for( int i = 1; i <= n; ++i) dfn[i] = -1;
	
	dfs(1, 0, 0); printf("%d\n", comp);
	for( int i = 1; i <= comp ; i++) {
		sort(v[i].begin(), v[i].end()); 
		v[i].resize( unique(v[i].begin(), v[i].end()) - v[i].begin() );
		for( vector <int> :: iterator it = v[i].begin(); it != v[i].end() ; ++it)
			printf("%d ", *it);
		printf("\n");
	}
	return 0;
}