Cod sursa(job #2365361)

Utilizator oldatlantianSerban Cercelescu oldatlantian Data 4 martie 2019 13:11:30
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.07 kb
#include <bits/stdc++.h>
using namespace std;

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

const int N = 1e5 + 5;


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

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


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

	for (auto v: g[u]) if (v != far && f[v])
		low[u] = min(low[u], lvl[v]);


	stk.push_back(u);
	for (auto v: g[u]) if (!f[v]) {
		dfs(v, u);
		if (low[v] >= lvl[u]) { // I'm at the top of a biconnected
			while (stk.back() != v) {
				bcx.back().push_back(stk.back());
				stk.pop_back(); }
			stk.pop_back();
			bcx.back().push_back(v);
			bcx.back().push_back(u);
			bcx.emplace_back(); }
		low[u] = min(low[u], low[v]); } }


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 i = 1; i <= n; ++i) if (!f[i]) {
		bcx.emplace_back();
		dfs(i); }

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

	return 0; }