Cod sursa(job #1195166)

Utilizator howsiweiHow Si Wei howsiwei Data 6 iunie 2014 16:45:14
Problema Componente biconexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include <iostream>
#include <cstdio>
#include <vector>
#include <stack>
using namespace std;

int n, m;
vector<vector<int>> adjl;
vector<int> level, low;
stack<int> t;
vector<vector<int>> bicons;

void dfs(int u, int p)
{
	if (p == -1) {
		level[u] = 0;
	}
	else {
		level[u] = level[p]+1;
	}
	low[u] = level[u];
	t.push(u);
	for (auto v: adjl[u]) {
		if (level[v] != -1) {
			low[u] = min(low[u], level[v]);
		}
		else {
			dfs(v, u);
			low[u] = min(low[u], low[v]);
		}
	}
	if (p != -1 && low[u] >= level[p]) {
		vector<int> bicon;
		while(t.top() != p) {
			bicon.push_back(t.top());
			t.pop();
		}
		bicon.push_back(p);
		bicons.push_back(bicon);
	}
}

int main()
{
	freopen("biconex.in", "r", stdin);
	freopen("biconex.out", "r", stdout);
	cin >> n >> m;
	adjl.resize(n);
	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		u--, v--;
		adjl[u].push_back(v);
		adjl[v].push_back(u);
	}
	level.assign(n, -1);
	low.resize(n);
	for (int i = 0; i < n; i++) {
		if (level[i] == -1) {
			dfs(i, -1);
		}
	}
	printf("%d\n", bicons.size());
	for (auto bicon: bicons) {
		for (auto u: bicon) {
			printf("%d ", u+1);
		}
		printf("\n");
	}
	return 0;
}