verify/yosupo/yosupo-biconnected_components.test.cpp

View this file on GitHub
Last update: 2022-07-23 18:03:31-04:00
Problem: https://judge.yosupo.jp/problem/biconnected_components

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/biconnected_components"

#include <bits/stdc++.h>
#include "../../library/graphs/biconnected-components.hpp"

int main() {
	using namespace std;
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, m;
	cin >> n >> m;
	vector<vector<int>> g(n);
	while (m--) {
		int u, v;
		cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	BiConnectedComponents bc(g);
	vector<vector<int>> ans;
	vector<int> used(n);
	for (auto& v : bc.bc) {
		vector<int> z;
		for (auto p : v) {
			z.push_back(p.first);
			z.push_back(p.second);
		}
		sort(z.begin(), z.end());
		z.erase(unique(z.begin(), z.end()), z.end());
		ans.push_back(z);
		for (int x : z) {
			used[x] = true;
		}
	}
	for (int i = 0; i < n; ++i) {
		if (!used[i]) {
			ans.push_back({i});
		}
	}
	cout << ans.size() << '\n';
	for (auto& z : ans) {
		cout << z.size() << ' ';
		for (int x : z) {
			cout << x << ' ';
		}
		cout << '\n';
	}
	return 0;
}

#define PROBLEM "https://judge.yosupo.jp/problem/biconnected_components"

#include <bits/stdc++.h>


template <typename G>
struct LowLink {
	int N;
	const G& g;
	std::vector<int> ord, low, articulation;
	std::vector<std::pair<int, int>> bridge;

	LowLink(const G& _g) : g(_g) {
		N = (int)g.size();
		ord.resize(N, -1);
		low.resize(N, -1);
		int k = 0;
		for (int i = 0; i < N; i++)
			if (ord[i] == -1) k = dfs(i, k, -1);
	}

	int dfs(int idx, int k, int par) {
		low[idx] = (ord[idx] = k++);
		int cnt = 0;
		bool is_arti = false, flg = false;
		for (auto &to : g[idx]) {
			if (ord[to] == -1) {
				cnt++;
				k = dfs(to, k, idx);
				low[idx] = std::min(low[idx], low[to]);
				is_arti |= (par != -1) && (low[to] >= ord[idx]);
				if (ord[idx] < low[to]) {
					bridge.emplace_back(std::minmax(idx, (int)to));
				}
			} else if (to != par || std::exchange(flg, true)) {
				low[idx] = std::min(low[idx], ord[to]);
			}
		}
		is_arti |= par == -1 && cnt > 1;
		if (is_arti) articulation.push_back(idx);
		return k;
	}
};

template <typename G>
struct BiConnectedComponents : LowLink<G> {
	using LL = LowLink<G>;

	std::vector<int> used;
	std::vector<std::vector<std::pair<int, int>>> bc; // will not include BCC's of size 1!
	std::vector<std::pair<int, int>> tmp;

	BiConnectedComponents(const G& _g) : LL(_g) { build(); }

	void build() {
		used.assign(this->g.size(), 0);
		for (int i = 0; i < (int)used.size(); i++) {
			if (!used[i]) dfs(i, -1);
		}
	}

	void dfs(int idx, int par) {
		used[idx] = true;
		for (auto& to : this->g[idx]) {
			if (to == par) continue;
			if (!used[to] || this->ord[to] < this->ord[idx]) {
				tmp.emplace_back(std::minmax(idx, to));
			}
			if (!used[to]) {
				dfs(to, idx);
				if (this->low[to] >= this->ord[idx]) {
					bc.emplace_back();
					while (true) {
						auto e = tmp.back();
						bc.back().emplace_back(e);
						tmp.pop_back();
						if (e.first == std::min(idx, to) && e.second == std::max(idx, to)) {
							break;
						}
					}
				}
			}
		}
	}
};

int main() {
	using namespace std;
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, m;
	cin >> n >> m;
	vector<vector<int>> g(n);
	while (m--) {
		int u, v;
		cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	BiConnectedComponents bc(g);
	vector<vector<int>> ans;
	vector<int> used(n);
	for (auto& v : bc.bc) {
		vector<int> z;
		for (auto p : v) {
			z.push_back(p.first);
			z.push_back(p.second);
		}
		sort(z.begin(), z.end());
		z.erase(unique(z.begin(), z.end()), z.end());
		ans.push_back(z);
		for (int x : z) {
			used[x] = true;
		}
	}
	for (int i = 0; i < n; ++i) {
		if (!used[i]) {
			ans.push_back({i});
		}
	}
	cout << ans.size() << '\n';
	for (auto& z : ans) {
		cout << z.size() << ' ';
		for (int x : z) {
			cout << x << ' ';
		}
		cout << '\n';
	}
	return 0;
}