Cod sursa(job #3297869)

Utilizator raresgoidescuGoidescu Rares-Stefan raresgoidescu Data 23 mai 2025 23:07:54
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.15 kb
#include <iostream>
#include <vector>
#include <stack>
#include <set>

const int NMAX = (int)1e5 + 5;

int n, m;
int timestamp;
std::vector<int> adj[NMAX];
std::vector<int> discovery_time;
std::vector<int> low_link;
std::vector<int> parent;
std::stack<std::pair<int, int> > edge_stack;
std::vector<std::set<int> > bccs;

void dfs_bcc(int node, int p) {
	discovery_time[node] = low_link[node] = timestamp++;

	parent[node] = p;

	for (auto &neigh : adj[node]) {
		if (neigh == p) {
			continue;
		}

		if (discovery_time[neigh] != -1 && discovery_time[neigh] < discovery_time[node]) {
			// means it's a back-edge
			edge_stack.push({node, neigh});

			low_link[node] = std::min(low_link[node], discovery_time[neigh]);
		}

		if (discovery_time[neigh] == -1) {
			// neigh is unvisited
			edge_stack.push({node, neigh});

			dfs_bcc(neigh, node);

			// node can reach what neigh can
			low_link[node] = std::min(low_link[node], low_link[neigh]);

			if (low_link[neigh] >= discovery_time[node]) {
				// bcc found
				std::set<int> vertices;

				while (!edge_stack.empty()) {
					std::pair<int, int> edge = edge_stack.top();
					edge_stack.pop();

					vertices.insert(edge.first);
					vertices.insert(edge.second);

					if (edge.first == node && edge.second == neigh) {
						break;
					}
				}

				bccs.push_back(vertices);
			}
		}
	}
}

int main(void)
{
#ifndef LOCAL
	freopen("biconex.in", "r", stdin);
	freopen("biconex.out", "w", stdout);
#endif

	std::ios::sync_with_stdio(false);
	std::cin.tie(0);

	std::cin >> n >> m;

	for (int i = 0; i < m; ++i) {
		int u, v;
		std::cin >> u >> v;

		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	discovery_time.resize(n + 1);
	parent.resize(n + 1);
	low_link.resize(n + 1);

	discovery_time.assign(discovery_time.size(), -1); // unvisited
	low_link.assign(low_link.size(), -1);
	parent.assign(parent.size(), 0);

	for (int i = 1; i <= n; ++i) {
		if (discovery_time[i]  == -1) {
			dfs_bcc(i, 0);
		}
	}

	std::cout << bccs.size() << '\n';
	for (auto &bcc : bccs) {
		bool first = true;
		for (auto &elem : bcc) {
			if (!first) {
				std::cout << " ";
			}
			std::cout << elem;
			first = false;
		}
		std::cout << '\n';
	}

	return 0;
}