Cod sursa(job #2799769)

Utilizator stefdascalescuStefan Dascalescu stefdascalescu Data 13 noiembrie 2021 13:42:54
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.46 kb
#include <cassert>
#include <cstdio>
#include <vector>
#include <stack>
 
#define MAXN 100000
 
#define MIN(a, b) ((a) < (b) ? (a) : (b))
 
std::vector<int> edges[MAXN];
 
bool viz[MAXN];
int nivel[MAXN];
int low[MAXN];
 
std::stack<int> stack;
 
std::vector<int> ret[MAXN];
size_t k = 0;
 
void
dfs (int nod, int parent = -1) {
	viz[nod] = true;
	low[nod] = nivel[nod];
	stack.emplace(nod);
 
	for (auto to: edges[nod]) {
		if (to == parent)
			continue;
		if (viz[to]) {
			low[nod] = MIN(low[nod], nivel[to]);
			continue;
		}
 
		nivel[to] = nivel[nod] + 1;
		dfs(to, nod);
 
		low[nod] = MIN(low[nod], low[to]);
 
		if (nivel[nod] < low[to]) {
			/* Muchie critică de la nod la to */
		}
 
		if (nivel[nod] == low[nod]) {
			/* Nod critic */
		}
 
		if (nivel[nod] == low[nod] || nivel[nod] <= low[to]) {
			int last;
			do {
				last = stack.top();
				stack.pop();
				ret[k].emplace_back(last);
			} while (last != to);
 
			ret[k].emplace_back(nod);
			++ k;
		}
	}
}
 
int main () {
	int n, m;
	int i;
 
	freopen("biconex.in", "r", stdin);
	freopen("biconex.out", "w", stdout);
 
	scanf("%d%d", &n, &m);
 
	for (i = 0; i != m; ++ i) {
		int de, la;
 
		scanf("%d%d", &de, &la);
		-- de, -- la;
 
		edges[de].emplace_back(la);
		edges[la].emplace_back(de);
	}
 
	dfs(0);
 
	printf("%zu\n", k);
 
	for (i = 0; i != k; ++ i) {
		for (auto val: ret[i])
			printf("%d ", val + 1);
		putchar('\n');
	}
}