Block Cut Tree

graph/block_cut_tree.hpp · GitHub で見る

共通ページ

無向グラフを二重頂点連結成分に分解し、成分と関節点を頂点とする Block Cut Tree を構築します。元のグラフが非連結なら森になります。

#include "lib/graph/block_cut_tree.hpp"

BlockCutTree graph(4);
graph.add_edge(0, 1);
graph.add_edge(1, 2);
graph.add_edge(2, 0);
graph.add_edge(2, 3);
graph.build();

assert(graph.block_count() == 2);
assert(graph.is_articulation(2));
assert(graph.node_id[0] == graph.node_id[1]);
const auto &forest = graph.tree; // vector<vector<int>> の無向森
assert(forest.size() == 3);
auto blocks = graph.groups();  // {0,1,2} と {2,3}（順序未指定）

頂点番号は 0 始まりです。多重辺・孤立点・非連結グラフ・空グラフに対応します。自己ループは分解に影響しません。橋の両端も 1 成分、孤立点も 1 頂点の成分とします。関節点は複数の成分に属します。

操作・メンバー	内容・返り値	計算量
`BlockCutTree(n = 0)`	元の頂点数を指定	\(O(1)\)
`add_edge(u,v)`	無向辺を追加し、0 始まりの辺 ID を返す	償却 \(O(1)\)
`build()`	成分・関節点・森を構築。辺を追加した後は再実行	\(O(n+m)\)
`build_components()`	成分・関節点・頂点の所属を構築。`tree` は空にする	\(O(n+m)\)
`block_count()` / `node_count()`	成分数／森の頂点数	\(O(1)\)
`group(c)`	成分 `c` の元頂点を `span<const int>` で取得	\(O(1)\)
`groups()`	全成分の元頂点を `vector<vector<int>>` にコピー	\(O(n)\)
`articulation` / `is_articulation(v)`	関節点の一覧／元頂点 `v` が関節点か	\(O(1)\)
`node_id[v]`	元頂点 `v` に対応する森の頂点番号	\(O(1)\)
`tree[t]`	森の頂点 `t` の隣接頂点一覧	\(O(1)\)
`is_block(t)`	森の頂点 `t` が成分を表すか	\(O(1)\)
`vertex(t)`	関節点の頂点なら元頂点番号、成分の頂点なら `-1`	\(O(1)\)
`n` / `edges[id]`	元の頂点数／辺の両端	\(O(1)\)

成分数を \(B\)、関節点数を \(A\) とすると、森の頂点番号は [0,B) が成分、[B,B+A) が関節点です。関節点の頂点は、その関節点を含む全ての成分の頂点と結ばれます。node_id[v] は、関節点ならその頂点、そうでなければ所属する成分の頂点を指します。

元の頂点 u,v の間を調べるときは、森の node_id[u],node_id[v] を使います。異なる木に属するなら元のグラフでも非連結です。木上の経路の内側にある関節点は、元のグラフで u,v を分離する頂点になります。

結果は build() または build_components() 後に参照してください。build_components() では tree は空になりますが、成分・関節点・頂点番号の問い合わせは利用できます。成分 ID と成分内の頂点順は未指定です。group() の参照は再構築・代入・破棄で無効になります。公開配列は直接書き換えず、辺の追加には add_edge() を使ってください。追加前に edges.reserve(m) で領域を予約できます。

頂点数は INT_MAX/2 以下、辺数は INT_MAX/2 以下とします。頂点数を \(n\)、辺数を \(m\) として、構築は \(O(n+m)\) 時間・空間、成分と森の保持は \(O(n)\) 空間です。

依存ライブラリ

無向グラフの CSR

検証コード

test/biconnected_components.test.cpp

コード

#line 1 "graph/block_cut_tree.hpp"

#line 1 "components/undirected_csr.hpp"

#include <cassert>
#include <cstddef>
#include <limits>
#include <memory>
#include <span>
#include <type_traits>
#include <utility>
#include <vector>

namespace undirected_csr_detail {
template <class Arc>
void build(int n, std::span<const std::pair<int, int>> edges, std::vector<int>& start, std::unique_ptr<Arc[]>& adj) {
	assert(0 <= n && n < std::numeric_limits<int>::max());
	assert(edges.size() <= std::size_t(std::numeric_limits<int>::max() / 2));
	start.assign(std::size_t(n) + 1, 0);
	for (auto [u, v] : edges) {
		assert(0 <= u && u < n && 0 <= v && v < n);
		++start[u + 1], ++start[v + 1];
	}
	for (int v = 0; v < n; ++v) start[v + 1] += start[v];
	adj.reset(new Arc[2 * edges.size()]);
	std::vector<int> cursor(start.begin(), start.end() - 1);
	for (int i = 0; i < static_cast<int>(edges.size()); ++i) {
		auto [u, v] = edges[i];
		if constexpr (std::is_same_v<Arc, int>) adj[cursor[u]++] = v, adj[cursor[v]++] = u;
		else adj[cursor[u]++] = {v, i}, adj[cursor[v]++] = {u, i};
	}
}
}

struct UndirectedCSR {
	struct Arc { int to, id; };
	int n;
	std::vector<int> start;
	std::unique_ptr<Arc[]> adj;
	UndirectedCSR(int n, std::span<const std::pair<int, int>> edges) : n(n) {
		undirected_csr_detail::build(n, edges, start, adj);
	}
	std::span<const Arc> operator[](int v) const {
		assert(0 <= v && v < n);
		return {adj.get() + start[v], std::size_t(start[v + 1] - start[v])};
	}
};

struct UndirectedVertexCSR {
	int n;
	std::vector<int> start;
	std::unique_ptr<int[]> adj;
	UndirectedVertexCSR(int n, std::span<const std::pair<int, int>> edges) : n(n) {
		undirected_csr_detail::build(n, edges, start, adj);
	}
	std::span<const int> operator[](int v) const {
		assert(0 <= v && v < n);
		return {adj.get() + start[v], std::size_t(start[v + 1] - start[v])};
	}
};

#line 5 "graph/block_cut_tree.hpp"
#include <algorithm>

class BlockCutTree {
	struct Frame { int v, next, low; };
	bool built_ = false;
	std::vector<int> vertices_, boundaries_;
	void check_([[maybe_unused]] int v) const { assert(built_ && 0 <= v && v < n); }

public:
	int n;
	std::vector<std::pair<int, int>> edges;
	std::vector<int> node_id, articulation;
	std::vector<std::vector<int>> tree;

explicit BlockCutTree(int n = 0) : n(n) {
		assert(0 <= n && n <= std::numeric_limits<int>::max() / 2);
	}
	int add_edge(int u, int v) {
		assert(0 <= u && u < n && 0 <= v && v < n);
		assert(edges.size() < std::size_t(std::numeric_limits<int>::max() / 2));
		built_ = false;
		int id = static_cast<int>(edges.size());
		edges.emplace_back(u, v);
		return id;
	}
	void build() { build_impl(true); }
	void build_components() { build_impl(false); }

private:
	void build_impl(bool build_tree) {
		built_ = false;
		UndirectedVertexCSR graph(n, edges);
		std::vector<int> ord(n, -1), active;
		std::vector<Frame> stack;
		active.reserve(n), stack.reserve(n);
		vertices_.clear(), boundaries_.assign(1, 0);
		vertices_.reserve(n);
		node_id.assign(n, -1), articulation.clear(), tree.clear();
		int timer = 0;
		auto append = [&](int v, int block) {
			vertices_.push_back(v);
			node_id[v] = node_id[v] == -1 ? block : -2;
		};
		for (int root = 0; root < n; ++root) if (ord[root] == -1) {
			ord[root] = timer++;
			active.push_back(root);
			stack.push_back({root, graph.start[root], ord[root]});
			while (!stack.empty()) {
				auto& frame = stack.back();
				int v = frame.v;
				if (frame.next == graph.start[v + 1]) {
					int value = frame.low;
					stack.pop_back();
					if (stack.empty()) {
						active.pop_back();
						if (node_id[v] == -1) {
							append(v, static_cast<int>(boundaries_.size()) - 1);
							boundaries_.push_back(static_cast<int>(vertices_.size()));
						}
					} else {
						int p = stack.back().v;
						stack.back().low = std::min(stack.back().low, value);
						if (value >= ord[p]) {
							int block = static_cast<int>(boundaries_.size()) - 1, u;
							append(p, block);
							do {
								u = active.back();
								active.pop_back();
								append(u, block);
							} while (u != v);
							boundaries_.push_back(static_cast<int>(vertices_.size()));
						}
					}
					continue;
				}
				while (frame.next != graph.start[v + 1]) {
					int to = graph.adj[frame.next++];
					if (ord[to] != -1) frame.low = std::min(frame.low, ord[to]);
					else {
						ord[to] = timer++;
						active.push_back(to);
						stack.push_back({to, graph.start[to], ord[to]});
						break;
					}
				}
			}
		}
		int blocks = static_cast<int>(boundaries_.size()) - 1;
		for (int v = 0; v < n; ++v) if (node_id[v] == -2) {
			node_id[v] = blocks + static_cast<int>(articulation.size());
			articulation.push_back(v);
		}
		if (!build_tree) { built_ = true; return; }
		tree.resize(std::size_t(blocks) + articulation.size());
		std::vector<int> degree(tree.size());
		for (int c = 0; c < blocks; ++c)
			for (int i = boundaries_[c]; i < boundaries_[c + 1]; ++i) {
				int v = node_id[vertices_[i]];
				if (v >= blocks) ++degree[c], ++degree[v];
			}
		for (std::size_t v = 0; v < tree.size(); ++v) tree[v].reserve(degree[v]);
		for (int c = 0; c < blocks; ++c)
			for (int i = boundaries_[c]; i < boundaries_[c + 1]; ++i) {
				int v = node_id[vertices_[i]];
				if (v >= blocks) tree[c].push_back(v), tree[v].push_back(c);
			}
		built_ = true;
	}

public:
	int block_count() const { assert(built_); return static_cast<int>(boundaries_.size()) - 1; }
	int node_count() const { assert(built_); return block_count() + static_cast<int>(articulation.size()); }
	bool is_articulation(int v) const { check_(v); return node_id[v] >= block_count(); }
	bool is_block(int node) const { assert(built_ && 0 <= node && node < node_count()); return node < block_count(); }
	int vertex(int node) const {
		assert(built_ && 0 <= node && node < node_count());
		return node < block_count() ? -1 : articulation[node - block_count()];
	}
	std::span<const int> group(int block) const {
		assert(built_ && 0 <= block && block < block_count());
		return {vertices_.data() + boundaries_[block], std::size_t(boundaries_[block + 1] - boundaries_[block])};
	}
	std::vector<std::vector<int>> groups() const {
		std::vector<std::vector<int>> result(block_count());
		for (int c = 0; c < block_count(); ++c) {
			auto members = group(c);
			result[c].assign(members.begin(), members.end());
		}
		return result;
	}
};

#ifndef BLOCK_CUT_TREE_HPP
#define BLOCK_CUT_TREE_HPP

#include "../components/undirected_csr.hpp"
#include <algorithm>

class BlockCutTree {
	struct Frame { int v, next, low; };
	bool built_ = false;
	std::vector<int> vertices_, boundaries_;
	void check_([[maybe_unused]] int v) const { assert(built_ && 0 <= v && v < n); }

  public:
	int n;
	std::vector<std::pair<int, int>> edges;
	std::vector<int> node_id, articulation;
	std::vector<std::vector<int>> tree;

	explicit BlockCutTree(int n = 0) : n(n) {
		assert(0 <= n && n <= std::numeric_limits<int>::max() / 2);
	}
	int add_edge(int u, int v) {
		assert(0 <= u && u < n && 0 <= v && v < n);
		assert(edges.size() < std::size_t(std::numeric_limits<int>::max() / 2));
		built_ = false;
		int id = static_cast<int>(edges.size());
		edges.emplace_back(u, v);
		return id;
	}
	void build() { build_impl(true); }
	void build_components() { build_impl(false); }

  private:
	void build_impl(bool build_tree) {
		built_ = false;
		UndirectedVertexCSR graph(n, edges);
		std::vector<int> ord(n, -1), active;
		std::vector<Frame> stack;
		active.reserve(n), stack.reserve(n);
		vertices_.clear(), boundaries_.assign(1, 0);
		vertices_.reserve(n);
		node_id.assign(n, -1), articulation.clear(), tree.clear();
		int timer = 0;
		auto append = [&](int v, int block) {
			vertices_.push_back(v);
			node_id[v] = node_id[v] == -1 ? block : -2;
		};
		for (int root = 0; root < n; ++root) if (ord[root] == -1) {
			ord[root] = timer++;
			active.push_back(root);
			stack.push_back({root, graph.start[root], ord[root]});
			while (!stack.empty()) {
				auto& frame = stack.back();
				int v = frame.v;
				if (frame.next == graph.start[v + 1]) {
					int value = frame.low;
					stack.pop_back();
					if (stack.empty()) {
						active.pop_back();
						if (node_id[v] == -1) {
							append(v, static_cast<int>(boundaries_.size()) - 1);
							boundaries_.push_back(static_cast<int>(vertices_.size()));
						}
					} else {
						int p = stack.back().v;
						stack.back().low = std::min(stack.back().low, value);
						if (value >= ord[p]) {
							int block = static_cast<int>(boundaries_.size()) - 1, u;
							append(p, block);
							do {
								u = active.back();
								active.pop_back();
								append(u, block);
							} while (u != v);
							boundaries_.push_back(static_cast<int>(vertices_.size()));
						}
					}
					continue;
				}
				while (frame.next != graph.start[v + 1]) {
					int to = graph.adj[frame.next++];
					if (ord[to] != -1) frame.low = std::min(frame.low, ord[to]);
					else {
						ord[to] = timer++;
						active.push_back(to);
						stack.push_back({to, graph.start[to], ord[to]});
						break;
					}
				}
			}
		}
		int blocks = static_cast<int>(boundaries_.size()) - 1;
		for (int v = 0; v < n; ++v) if (node_id[v] == -2) {
			node_id[v] = blocks + static_cast<int>(articulation.size());
			articulation.push_back(v);
		}
		if (!build_tree) { built_ = true; return; }
		tree.resize(std::size_t(blocks) + articulation.size());
		std::vector<int> degree(tree.size());
		for (int c = 0; c < blocks; ++c)
			for (int i = boundaries_[c]; i < boundaries_[c + 1]; ++i) {
				int v = node_id[vertices_[i]];
				if (v >= blocks) ++degree[c], ++degree[v];
			}
		for (std::size_t v = 0; v < tree.size(); ++v) tree[v].reserve(degree[v]);
		for (int c = 0; c < blocks; ++c)
			for (int i = boundaries_[c]; i < boundaries_[c + 1]; ++i) {
				int v = node_id[vertices_[i]];
				if (v >= blocks) tree[c].push_back(v), tree[v].push_back(c);
			}
		built_ = true;
	}

  public:
	int block_count() const { assert(built_); return static_cast<int>(boundaries_.size()) - 1; }
	int node_count() const { assert(built_); return block_count() + static_cast<int>(articulation.size()); }
	bool is_articulation(int v) const { check_(v); return node_id[v] >= block_count(); }
	bool is_block(int node) const { assert(built_ && 0 <= node && node < node_count()); return node < block_count(); }
	int vertex(int node) const {
		assert(built_ && 0 <= node && node < node_count());
		return node < block_count() ? -1 : articulation[node - block_count()];
	}
	std::span<const int> group(int block) const {
		assert(built_ && 0 <= block && block < block_count());
		return {vertices_.data() + boundaries_[block], std::size_t(boundaries_[block + 1] - boundaries_[block])};
	}
	std::vector<std::vector<int>> groups() const {
		std::vector<std::vector<int>> result(block_count());
		for (int c = 0; c < block_count(); ++c) {
			auto members = group(c);
			result[c].assign(members.begin(), members.end());
		}
		return result;
	}
};

#endif

#line 1 "graph/block_cut_tree.hpp"



#line 1 "components/undirected_csr.hpp"



#include <cassert>
#include <cstddef>
#include <limits>
#include <memory>
#include <span>
#include <type_traits>
#include <utility>
#include <vector>

namespace undirected_csr_detail {
template <class Arc>
void build(int n, std::span<const std::pair<int, int>> edges, std::vector<int>& start, std::unique_ptr<Arc[]>& adj) {
	assert(0 <= n && n < std::numeric_limits<int>::max());
	assert(edges.size() <= std::size_t(std::numeric_limits<int>::max() / 2));
	start.assign(std::size_t(n) + 1, 0);
	for (auto [u, v] : edges) {
		assert(0 <= u && u < n && 0 <= v && v < n);
		++start[u + 1], ++start[v + 1];
	}
	for (int v = 0; v < n; ++v) start[v + 1] += start[v];
	adj.reset(new Arc[2 * edges.size()]);
	std::vector<int> cursor(start.begin(), start.end() - 1);
	for (int i = 0; i < static_cast<int>(edges.size()); ++i) {
		auto [u, v] = edges[i];
		if constexpr (std::is_same_v<Arc, int>) adj[cursor[u]++] = v, adj[cursor[v]++] = u;
		else adj[cursor[u]++] = {v, i}, adj[cursor[v]++] = {u, i};
	}
}
}

struct UndirectedCSR {
	struct Arc { int to, id; };
	int n;
	std::vector<int> start;
	std::unique_ptr<Arc[]> adj;
	UndirectedCSR(int n, std::span<const std::pair<int, int>> edges) : n(n) {
		undirected_csr_detail::build(n, edges, start, adj);
	}
	std::span<const Arc> operator[](int v) const {
		assert(0 <= v && v < n);
		return {adj.get() + start[v], std::size_t(start[v + 1] - start[v])};
	}
};

struct UndirectedVertexCSR {
	int n;
	std::vector<int> start;
	std::unique_ptr<int[]> adj;
	UndirectedVertexCSR(int n, std::span<const std::pair<int, int>> edges) : n(n) {
		undirected_csr_detail::build(n, edges, start, adj);
	}
	std::span<const int> operator[](int v) const {
		assert(0 <= v && v < n);
		return {adj.get() + start[v], std::size_t(start[v + 1] - start[v])};
	}
};


#line 5 "graph/block_cut_tree.hpp"
#include <algorithm>

class BlockCutTree {
	struct Frame { int v, next, low; };
	bool built_ = false;
	std::vector<int> vertices_, boundaries_;
	void check_([[maybe_unused]] int v) const { assert(built_ && 0 <= v && v < n); }

  public:
	int n;
	std::vector<std::pair<int, int>> edges;
	std::vector<int> node_id, articulation;
	std::vector<std::vector<int>> tree;

	explicit BlockCutTree(int n = 0) : n(n) {
		assert(0 <= n && n <= std::numeric_limits<int>::max() / 2);
	}
	int add_edge(int u, int v) {
		assert(0 <= u && u < n && 0 <= v && v < n);
		assert(edges.size() < std::size_t(std::numeric_limits<int>::max() / 2));
		built_ = false;
		int id = static_cast<int>(edges.size());
		edges.emplace_back(u, v);
		return id;
	}
	void build() { build_impl(true); }
	void build_components() { build_impl(false); }

  private:
	void build_impl(bool build_tree) {
		built_ = false;
		UndirectedVertexCSR graph(n, edges);
		std::vector<int> ord(n, -1), active;
		std::vector<Frame> stack;
		active.reserve(n), stack.reserve(n);
		vertices_.clear(), boundaries_.assign(1, 0);
		vertices_.reserve(n);
		node_id.assign(n, -1), articulation.clear(), tree.clear();
		int timer = 0;
		auto append = [&](int v, int block) {
			vertices_.push_back(v);
			node_id[v] = node_id[v] == -1 ? block : -2;
		};
		for (int root = 0; root < n; ++root) if (ord[root] == -1) {
			ord[root] = timer++;
			active.push_back(root);
			stack.push_back({root, graph.start[root], ord[root]});
			while (!stack.empty()) {
				auto& frame = stack.back();
				int v = frame.v;
				if (frame.next == graph.start[v + 1]) {
					int value = frame.low;
					stack.pop_back();
					if (stack.empty()) {
						active.pop_back();
						if (node_id[v] == -1) {
							append(v, static_cast<int>(boundaries_.size()) - 1);
							boundaries_.push_back(static_cast<int>(vertices_.size()));
						}
					} else {
						int p = stack.back().v;
						stack.back().low = std::min(stack.back().low, value);
						if (value >= ord[p]) {
							int block = static_cast<int>(boundaries_.size()) - 1, u;
							append(p, block);
							do {
								u = active.back();
								active.pop_back();
								append(u, block);
							} while (u != v);
							boundaries_.push_back(static_cast<int>(vertices_.size()));
						}
					}
					continue;
				}
				while (frame.next != graph.start[v + 1]) {
					int to = graph.adj[frame.next++];
					if (ord[to] != -1) frame.low = std::min(frame.low, ord[to]);
					else {
						ord[to] = timer++;
						active.push_back(to);
						stack.push_back({to, graph.start[to], ord[to]});
						break;
					}
				}
			}
		}
		int blocks = static_cast<int>(boundaries_.size()) - 1;
		for (int v = 0; v < n; ++v) if (node_id[v] == -2) {
			node_id[v] = blocks + static_cast<int>(articulation.size());
			articulation.push_back(v);
		}
		if (!build_tree) { built_ = true; return; }
		tree.resize(std::size_t(blocks) + articulation.size());
		std::vector<int> degree(tree.size());
		for (int c = 0; c < blocks; ++c)
			for (int i = boundaries_[c]; i < boundaries_[c + 1]; ++i) {
				int v = node_id[vertices_[i]];
				if (v >= blocks) ++degree[c], ++degree[v];
			}
		for (std::size_t v = 0; v < tree.size(); ++v) tree[v].reserve(degree[v]);
		for (int c = 0; c < blocks; ++c)
			for (int i = boundaries_[c]; i < boundaries_[c + 1]; ++i) {
				int v = node_id[vertices_[i]];
				if (v >= blocks) tree[c].push_back(v), tree[v].push_back(c);
			}
		built_ = true;
	}

  public:
	int block_count() const { assert(built_); return static_cast<int>(boundaries_.size()) - 1; }
	int node_count() const { assert(built_); return block_count() + static_cast<int>(articulation.size()); }
	bool is_articulation(int v) const { check_(v); return node_id[v] >= block_count(); }
	bool is_block(int node) const { assert(built_ && 0 <= node && node < node_count()); return node < block_count(); }
	int vertex(int node) const {
		assert(built_ && 0 <= node && node < node_count());
		return node < block_count() ? -1 : articulation[node - block_count()];
	}
	std::span<const int> group(int block) const {
		assert(built_ && 0 <= block && block < block_count());
		return {vertices_.data() + boundaries_[block], std::size_t(boundaries_[block + 1] - boundaries_[block])};
	}
	std::vector<std::vector<int>> groups() const {
		std::vector<std::vector<int>> result(block_count());
		for (int c = 0; c < block_count(); ++c) {
			auto members = group(c);
			result[c].assign(members.begin(), members.end());
		}
		return result;
	}
};