Cod sursa(job #3262327)

Utilizator tryharderulbrebenel mihnea stefan tryharderul Data 9 decembrie 2024 18:55:36
Problema Componente biconexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.11 kb
#include <bits/stdc++.h>

using namespace std;

int main() {

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

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

	vector<vector<int>> g(n + 1);
	for(int i = 1; i <= m; i++) {
		int x, y;
		in >> x >> y;
		g[x].push_back(y);
		g[y].push_back(x);
	}

	vector<vector<int>> comps;
	vector<int> stk, num(n + 1), low(n + 1);
	function<void(int, int, int&)> dfs = [&](int node, int parent, int &timer) -> void {
		num[node] = low[node] = ++timer;
		stk.push_back(node);
		for(auto son : g[node]) {
			if(son == parent) { continue; }
			if(num[son]) {
				low[node] = min(low[node], num[son]);
			} else {
				dfs(son, node, timer);
				low[node] = min(low[node], low[son]);
				if(low[son] >= num[node]) {
					comps.push_back({node});
					while(comps.back().back() != son) {
						comps.back().push_back(stk.back());
						stk.pop_back();
					}
				}
			}
		}
	};

	int timer = 0;
	dfs(1, 0, timer);

	for(auto comp : comps) { 
		sort(comp.begin(), comp.end());
		for(auto node : comp) { 
			out << node << ' ';
		}
		out << '\n';
	}
	

	return 0;
}