Cod sursa(job #3030659)

Utilizator the_horoHorodniceanu Andrei the_horo Data 17 martie 2023 19:54:34
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.18 kb
#include <bits/stdc++.h>
using namespace std;

array<int, 100'010> level, low;

array<vector<int>, 100'010> edges;

vector<vector<int>> result;

void dfs(int node, int parent) {
	static stack<int> comp;
	
	low[node] = level[node];
	comp.emplace(node);

	for (auto to: edges[node]) {
		if (to == parent)
			continue;
		
		if (level[to] != -1) {
			low[node] = min(low[node], level[to]);
			continue;
		}

		level[to] = level[node] + 1;
		dfs(to, node);

		low[node] = min(low[node], low[to]);

		if (low[to] >= level[node]) {
			int last;
			result.emplace_back();
			do {
				result.back().emplace_back(last = comp.top());
				comp.pop();
			} while (last != to);
			
			result.back().emplace_back(node);
		}
	}
}

int main () {
	ifstream in("biconex.in");
	in.exceptions(in.failbit);
	ofstream out("biconex.out");
	out.exceptions(out.failbit);

	int n, m;
	in >> n >> m;

	for (int i = 0; i < m; ++ i) {
		int x, y;
		in >> x >> y;

		edges[x].emplace_back(y);
		edges[y].emplace_back(x);
	}

	std::fill_n(level.begin() + 1, n, -1);

	level[1] = 0;
	dfs(1, -1);

	out << result.size() << '\n';

	for (const auto &comp: result) {
		for (const auto &node: comp)
			out << node << ' ';
		out << '\n';
	}
}