Cod sursa(job #3197069)

Utilizator robeteaRobert Cristea robetea Data 25 ianuarie 2024 16:38:58
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.76 kb
#include <bits/stdc++.h>
#include <charconv>
#include <climits>
#include <fstream>
#include <string>

struct nod; std::vector<nod> noduri;
std::vector<int> articulatii;
std::stack<int> stack;
int componente = 0;

std::vector<char> output;
void push_output(int target) {
	while(stack.top() != target) {
		auto s = std::to_string(stack.top());
		for(auto x: s) output.emplace_back(x);
		output.emplace_back(' ');
		stack.pop();
	}
	auto s = std::to_string(stack.top());
	for(auto x: s) output.emplace_back(x);
	output.emplace_back(' ');
	output.emplace_back('\n');
	stack.pop();
}

struct nod : std::vector<int> {
	int depth;
	int lowpoint;
	bool visited;
	bool articulatie;

	nod() : depth(0), lowpoint(2e9), visited(false), articulatie(false) {}
};

void dfs(int nod_index, int depth, int parent) {
	stack.push(nod_index);
	auto& nod = noduri[nod_index];
	nod.visited = true;
	nod.depth = depth;
	nod.lowpoint = depth;

	for(auto i : nod) {
		auto& v = noduri[i];

		if(!v.visited) {
			dfs(i, depth + 1, nod_index);
			if(v.lowpoint >= nod.depth) {
				nod.articulatie = true;
				stack.push(nod_index);
				push_output(i);
				componente++;
			}

			nod.lowpoint = std::min(nod.lowpoint, v.lowpoint);
		}
		else if(i != parent)
			nod.lowpoint = std::min(nod.lowpoint, v.depth);
	}


	//if((depth != 0 && nod.articulatie) || (depth == 0 && nod.size() > 1))
	//	articulatii.push_back(nod_index);
}


int main() {
	freopen("biconex.in", "r", stdin);
	freopen("biconex.out", "w", stdout);

	int n, m; std::cin >> n >> m;
	noduri.resize(n + 1); 

	while(m--) {
		int a, b; std::cin >> a >> b;
		noduri[a].push_back(b);
		noduri[b].push_back(a);
	}

	dfs(1, 0, -1);
	//for(auto x: articulatii) std::cout << x << ' ';
	std::cout << componente << '\n';

	for(auto x : output) std::cout << x;

	return 0;
}