library/graphs/biconnected-components.hpp

View this file on GitHub
Last update: 2022-07-23 18:03:31-04:00
Include: #include "library/graphs/biconnected-components.hpp"

Depends on

library/graphs/low-link.hpp

Required by

library/graphs/block-cut-tree.hpp

Verified with

Code

#pragma once 

#include "low-link.hpp"

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

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