Cod sursa(job #2799707)

Utilizator schizofrenieShallan Davar schizofrenie Data 13 noiembrie 2021 13:25:32
Problema Componente biconexe Scor 42
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.33 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]) {
			while (stack.top() != nod) {
				ret[k].emplace_back(stack.top());
				stack.pop();
			}

			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');
	}
}