Cod sursa(job #3374009)

Utilizator lefterache_stefanLefterache Stefan lefterache_stefan Data 8 noiembrie 2026 14:14:02
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.96 kb
#include <bits/stdc++.h>

using namespace std;

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

const int MAXIM = 100005;
vector<int> graf[MAXIM];
int timp_vizitare[MAXIM], low[MAXIM], ultima_componenta[MAXIM];
int timp = 0;
vector<pair<int, int>> stiva_muchii;
vector<vector<int>> componente;

void adauga_componenta(const int nod, const int vecin) {
	componente.emplace_back();
	vector<int>& componenta = componente.back();
	const int id = (int)componente.size();

	while (true) {
		const pair<int, int> muchie = stiva_muchii.back();
		stiva_muchii.pop_back();

		if (ultima_componenta[muchie.first] != id) {
			ultima_componenta[muchie.first] = id;
			componenta.push_back(muchie.first);
		}
		if (ultima_componenta[muchie.second] != id) {
			ultima_componenta[muchie.second] = id;
			componenta.push_back(muchie.second);
		}

		if (muchie.first == nod && muchie.second == vecin) {
			break;
		}
	}
}

void dfs(const int nod, const int parinte) {
	timp_vizitare[nod] = low[nod] = ++timp;
	bool muchia_catre_parinte_ignorata = false;

	for (const int vecin : graf[nod]) {
		if (vecin == parinte && !muchia_catre_parinte_ignorata) {
			muchia_catre_parinte_ignorata = true;
			continue;
		}

		if (timp_vizitare[vecin] == 0) {
			stiva_muchii.push_back({nod, vecin});
			dfs(vecin, nod);
			low[nod] = min(low[nod], low[vecin]);

			if (low[vecin] >= timp_vizitare[nod]) {
				adauga_componenta(nod, vecin);
			}
		} else if (timp_vizitare[vecin] < timp_vizitare[nod]) {
			stiva_muchii.push_back({nod, vecin});
			low[nod] = min(low[nod], timp_vizitare[vecin]);
		}
	}
}

int main() {
	int n, m;
	fin >> n >> m;

	for (int i = 0; i < m; i++) {
		int x, y;
		fin >> x >> y;
		graf[x].push_back(y);
		graf[y].push_back(x);
	}
	for (int nod = 1; nod <= n; nod++) {
		if (timp_vizitare[nod] == 0) {
			dfs(nod, 0);
		}
	}

	fout << componente.size() << '\n';
	for (const vector<int>& componenta : componente) {
		for (const int nod : componenta) {
			fout << nod << ' ';
		}
		fout << '\n';
	}
}