Cod sursa(job #2286270)

Utilizator oldatlantianSerban Cercelescu oldatlantian Data 19 noiembrie 2018 23:39:16
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.06 kb
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

ifstream fi("biconex.in");
ofstream fo("biconex.out");

using pii = pair<int, int>;

const int N = 1e5 + 5;

vector<int> g[N];
int lvl[N], low[N];
bool f[N];

vector<vector<int>> bcx;
vector<pii> stk;
int n, m;

static void dfs(int u, int far = 0) {
	lvl[u] = low[u] = lvl[far] + 1;
	f[u] = true;

	int fst, snd;
	for (auto v: g[u]) if (v != far) {
		if (f[v]) {
			low[u] = min(low[u], lvl[v]);
			continue; }

		stk.emplace_back(u, v);
		dfs(v, u);
		low[u] = min(low[u], low[v]);
		if (low[v] >= lvl[u]) {
			bcx.emplace_back();
			do {
				tie(fst, snd) = tie(stk.back().x, stk.back().y);
				bcx.back().push_back(snd);
				stk.pop_back(); }
			while (fst != u);
			bcx.back().push_back(fst); } } }

int main() {
	fi >> n >> m;
	for (int u, v, i = 0; i < m; ++i) {
		fi >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u); }

	for (int u = 1; u <= n; ++u) if (!f[u])
		dfs(u);

	fo << bcx.size() << '\n';
	for (auto &c: bcx) {
		for (const auto &i: c)
			fo << i << ' ';
		fo << '\n'; }

	return 0; }