Cod sursa(job #2981191)

Utilizator apocal1ps13Stefan Oprea Antoniu apocal1ps13 Data 17 februarie 2023 14:56:54
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.25 kb
#include<iostream>
#include<fstream>
#include<vector>
#include<stack>
#include<algorithm>
std::ifstream in("biconex.in");
std::ofstream out("biconex.out");
using namespace std;
const int NMAX = 1e5;
vector<int>g[NMAX + 1], visited, low, tin, mark, ans[NMAX + 1];
int n, m, u, v, timer, cc;
stack<int>stiva;
void find_points(int node, int parent) {
	visited[node] = 1;
	stiva.push(node);
	tin[node] = low[node] = ++timer;
	for (auto i : g[node]) {
		if (i == parent) continue;
		if (visited[i])  low[node] = min(low[node], tin[i]);
		else {
			find_points(i, node);
			low[node] = min(low[node], low[i]);
			if (low[i] >= tin[node]) {
				cc++;
				while (!stiva.empty() && stiva.top() != i)
				{
					ans[cc].push_back(stiva.top());
					stiva.pop();
				}
				ans[cc].push_back(i);
				stiva.pop();
				ans[cc].push_back(node);
			}
		}
	}
}
int main() {
	in >> n >> m;
	low = tin = mark = visited = vector<int>(n + 1);
	while (m--) {
		in >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	for (int i = 1; i <= n; i++)
		if (!visited[i]) find_points(i, 0);
	out << cc << '\n';
	for (int i = 1; i <= cc; i++) {
		sort(ans[i].begin(), ans[i].end());
		for (auto j : ans[i]) out << j << " ";
		out << '\n';
	}
	return 0;
}