Cod sursa(job #3121021)

Utilizator matwudemagogul matwu Data 10 aprilie 2023 13:28:57
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.09 kb
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 1;
int n, m, cnt;
vector<int> liste[N];
stack<pair<int, int>> s;
vector<int> low(N), tin(N), viz(N);
vector<set<int>> comp;

void check(int x, int y) {
	int tz = 0, tj = 0;
	set<int> p;
	do {
		tz = s.top().first, tj = s.top().second;
		p.insert(tz);
		p.insert(tj);
		s.pop();
	} while (tz != x || tj != y);
	comp.push_back(p);
}
void dfs(int nod, int p) {

	tin[nod] = low[nod] = ++cnt;
	viz[nod] = 1;
	for (auto i : liste[nod]) {
		if (p == i) continue;
		if (viz[i]) {
			low[nod] = min(low[nod], tin[i]);
		}
		else {
			s.push({ nod, i });
			dfs(i, nod);
			low[nod] = min(low[nod], low[i]);
			if (low[i] >= tin[nod]) {
				check(nod, i);
			}
		}
	}
}
int main() {
	ifstream fin("biconex.in");
	ofstream fout("biconex.out");
	fin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int u, v;
		fin >> u >> v;
		liste[u].push_back(v);
		liste[v].push_back(u);
	}
	dfs(1, -1);

	fout << comp.size() << '\n';
	for (auto i : comp) {
		for (auto j : i) {
			fout << j << " ";
		}
		fout << '\n';
	}
}