Cod sursa(job #1701067)

Utilizator mihai995mihai995 mihai995 Data 12 mai 2016 03:50:30
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include <fstream>
#include <iostream>
#include <stack>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;

const int N = 1 + 1e5;

int depth[N];
vector<int> graph[N];
vector< vector<int> > C;
stack< pair<int, int> > stk;

void foundBCC(int X, int Y){
	vector<int> v;
	int x, y;
	do {
		x = stk.top().first;
		y = stk.top().second;
		stk.pop();
		v.push_back(x);
		v.push_back(y);
	} while (x != X && y != Y);
	sort( v.begin(), v.end() );
	v.resize( unique(v.begin(), v.end()) - v.begin() );
	C.push_back(v);
}
int dfs(int x, int T = -1, int D = 0){
	int H = depth[x] = D;
	for (int y : graph[x])
		if ( depth[y] == -1 ){
			stk.emplace(x, y);
			int h = dfs(y, x, D + 1);
			H = min(H, h);
			if ( h >= D ) foundBCC(x, y);
		} else if ( y != T )
			H = min(H, depth[y]);
	return H;
}
void biconex(int n){
	memset( depth, -1, sizeof(depth) );
	for (int i = 1; i <= n; i++)
		if ( depth[i] == -1 )
			dfs(i);
}
int main(){
	ifstream in("biconex.in");
	ofstream out("biconex.out");
	int n, m, x, y;

	in >> n >> m;
	while (m--){
		in >> x >> y;
		graph[x].push_back(y);
		graph[y].push_back(x);
	}

	biconex(n);

	out << C.size() << '\n';
	for (vector<int>& v : C){
		for (int x : v)
			out << x << ' ';
		out << '\n';
	}
	return 0;
}