Cod sursa(job #2811703)

Utilizator Langa_bLanga Radu Langa_b Data 2 decembrie 2021 22:29:14
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.46 kb
#include <fstream>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;
ifstream cin("biconex.in");
ofstream cout("biconex.out");
int n, m, T[100002], lvl[100002];
vector<vector<int>> adj, rez;
stack<pair<int, int>> st;
void dfs(int act, int prev, int nivel) {
	T[act] = lvl[act] = nivel;
	for (int i = 0; i < adj[act].size(); i++) {
		int nxt = adj[act][i];
		if (nxt == prev) {
			continue;
		}
		else {
			if (lvl[nxt] == -1) {
				st.push({ act, nxt });
				dfs(nxt, act, nivel + 1);
				T[act] = min(T[act], T[nxt]);
				if (T[nxt] >= lvl[act]) {
					int tx, ty;
					vector<int> inter;
					do {
						tx = st.top().first;
						ty = st.top().second;
						st.pop();
						inter.emplace_back(tx);
						inter.emplace_back(ty);
					} while (tx != act || ty != nxt);
					rez.emplace_back(inter);
				}
			}
			else {
				T[act] = min(T[act], lvl[nxt]);
			}
		}
	}
}
int main() {
	int n, m;
	cin >> n >> m;
	for (int i = 0; i <= n; i++) {
		adj.emplace_back(vector<int>());
		lvl[i] = -1;
	}
	for (int i = 1; i <= m; i++) {
		int x, y;
		cin >> x >> y;
		adj[x].emplace_back(y);
		adj[y].emplace_back(x);
	}
	dfs(1, 0, 1);
	cout << rez.size() << '\n';
	for (int i = 0; i < rez.size(); i++) {
		sort(rez[i].begin(), rez[i].end());
		cout << rez[i][0]<<' ';
		for (int j = 1; j < rez[i].size(); j++) {
			if (rez[i][j] != rez[i][j - 1]) {
				cout << rez[i][j] << ' ';
			}
		}
		cout << '\n';
	}
}