Cod sursa(job #3374204)

Utilizator george6115Gall George Cosmin george6115 Data 8 noiembrie 2026 20:25:45
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.68 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int N,M;
vector<vector<int>> lista, componente;
vector<int> nivel, low, tata, noduri;

void citire(){
	fin>>N>>M;
	lista.resize(N+1);
	nivel.resize(N+1, 0);
	low.resize(N+1, 0);
	tata.resize(N+1, 0);
	auto cm = M;
	while(cm){
		int x, y;
		fin>>x>>y;
		lista[x].push_back(y);
		lista[y].push_back(x);
		cm--;
	}
}

void dfs(int numar) {
	vector<int> stiva;
	stiva.push_back(numar);
	noduri.push_back(numar);
	nivel[numar]=1;
	low[numar]=1;

	while (!stiva.empty()) {
		auto u = stiva.back();
		if (!lista[u].empty()) {
			auto v = lista[u].back();
			lista[u].pop_back();
			if (v==tata[u])
				continue;
			if (nivel[v])
				low[u]=min(low[u], nivel[v]);
			else {
				tata[v]=u;
				nivel[v]=nivel[u]+1;
				low[v]=nivel[v];
				stiva.push_back(v);
				noduri.push_back(v);
			}
		} else {
			stiva.pop_back();
			auto p = tata[u];
			if (p) {
				low[p]=min(low[p], low[u]);
				if (low[u]>=nivel[p]) {
					vector<int> comp;
					while (noduri.back()!=u) {
						comp.push_back(noduri.back());
						noduri.pop_back();
					}
					comp.push_back(u);
					noduri.pop_back();
					comp.push_back(p);
					componente.push_back(comp);
				}
			}
		}
	}
	noduri.clear();
}

void componente_biconexe(){
	for (int i=1; i<=N; i++)
		if (!nivel[i])
			dfs(i);
}

void afisare(){
	fout<<componente.size()<<"\n";
	for (auto comp : componente) {
		for (auto x : comp)
			fout<<x<<" ";
		fout<<"\n";
	}
}

int main(){
	citire();
	componente_biconexe();
	afisare();
	return 0;
}