Cod sursa(job #2265877)

Utilizator oldatlantianSerban Cercelescu oldatlantian Data 21 octombrie 2018 20:34:37
Problema Componente biconexe Scor 46
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.94 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) {
	lvl[u] = low[u] = lvl[far] + 1;
	f[u] = true;

	stk.push_back(u);
	for (auto v: g[u]) if (v != far) {
		if (f[v]) {
			low[u] = min(low[u], lvl[v]);
			continue; }

		dfs(v, u);
		low[u] = min(low[u], low[v]);
		if (low[v] >= lvl[u]) {
			bcx.emplace_back();
			bcx.back().push_back(u);
			while (lvl[stk.back()] > lvl[u]) {
				bcx.back().push_back(stk.back());	
				stk.pop_back(); } } } }

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])
		dfs(i);

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

	return 0; }