Cod sursa(job #2938280)

Utilizator andrei_C1Andrei Chertes andrei_C1 Data 11 noiembrie 2022 22:10:54
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.02 kb
#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 1e5;

int N, M;
vector<int> adj[NMAX + 1];
int lev[NMAX + 1], low[NMAX + 1];
stack<int> st;
vector<vector<int>> bicomp;

void dfs(int u = 1, int v = 0) {
	lev[u] = low[u] = lev[v] + 1;
	st.push(u);

	for(const auto &it: adj[u]) if(it != v) {
		if(lev[it] == 0) {
			dfs(it, u);
			low[u] = min(low[u], low[it]);

			if(low[it] >= lev[u]) {
				bicomp.push_back({it, u});

				while(!st.empty() && st.top() != it) {
					bicomp.back().push_back(st.top());
					st.pop();
				}

				st.pop();
			}
		} else {
			low[u] = min(low[u], lev[it]);
		}
	}
}

int main() {
	ios_base :: sync_with_stdio(false);

	fin >> N >> M;

	for(int i = 1; i <= M; i++) {
		int u, v;
		fin >> u >> v;

		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	dfs();

	fout << bicomp.size() << '\n';

	for(auto &comp: bicomp) {
		for(const auto &it: comp) {
			fout << it << " ";
		}
		fout << '\n';
	}

	fin.close();
	fout.close();
	return 0;
}