二辺連結成分分解

graph/two_edge_connected_components.hpp · GitHub で見る

共通ページ

#include "lib/graph/two_edge_connected_components.hpp"

TwoEdgeConnectedComponents graph(4);
graph.add_edge(0, 1);
graph.add_edge(1, 2);
graph.add_edge(2, 0);
int bridge = graph.add_edge(2, 3);
graph.build();
bool same = graph.same(0, 2);
auto members = graph.group(graph.component[0]);
auto forest = graph.forest();

関数・メンバ	内容・返り値	計算量
TwoEdgeConnectedComponents(n = 0)	頂点数を指定して構築	\(O(1)\)
add_edge(u,v)	無向辺を追加し、0 始まりの辺 ID を返す	償却 \(O(1)\)
build()	二辺連結成分と橋を計算。辺を追加した後は再実行	\(O(n+m)\)
component_count()	成分数。空グラフでは 0	\(O(1)\)
component[v]	頂点 v が属する成分の ID	\(O(1)\)
same(u,v)	2 頂点が同じ成分に属するか	\(O(1)\)
group(c)	成分 c の頂点一覧を、コピーせず span<const int> で返す	\(O(1)\)
groups()	全成分の頂点一覧を vector<vector<int>> にコピーして返す	\(O(n+k)\)
bridges	橋の辺 ID の一覧	\(O(1)\)
is_bridge(id)	辺 id が橋か	\(O(1)\)
forest()	各成分を縮約した橋の森を vector<vector<Arc>> で返す	\(O(k+b)\)
Arc::to / Arc::id	森の隣接成分 ID／元のグラフの辺 ID	\(O(1)\)
n / edges[id]	頂点数／辺の両端	\(O(1)\)

無向グラフの橋を全て除いた連結成分を求めます。頂点番号は 0 始まりです。多重辺・自己ループ・非連結グラフ・孤立点・頂点数 0 に対応します。孤立点も 1 個の成分になります。

build() の後に結果を参照してください。成分 ID は 0 から component_count()-1 までで、DFS の完了順です。成分内の頂点と橋の順序は未指定です。辺を追加して再構築すると、成分 ID が変わることがあります。

group(c) の参照先は再構築・代入・破棄で無効になります。groups() と forest() は独立したコピーです。森の辺は両方向に格納し、平行辺や自己ループは残りません。元のグラフが非連結なら、結果も森になります。

n・component・bridges・構築済みの edges は直接書き換えないでください。辺の追加前に edges.reserve(m) で領域を確保できます。頂点数は INT_MAX 未満、辺数は INT_MAX/2 以下としてください。

CSR と反復 DFS を使います。成分が確定するたびに頂点スタックから取り出し、保存する頂点一覧と作業用スタックに同じ配列を使います。関節点も必要な場合は Low-Link を使えます。

頂点数を \(n\)、辺数を \(m\)、成分数を \(k\)、橋の本数を \(b\) とすると、build() は \(O(n+m)\) 時間・空間です。add_edge は償却 \(O(1)\)、group・same・component_count・is_bridge は \(O(1)\) 時間です。groups は \(O(n+k)\)、forest は \(O(k+b)\) 時間・追加空間です。

依存ライブラリ

• Default Init Allocator
• 無向グラフの CSR

検証コード

• test/two_edge_connected_components.test.cpp

コード

#ifndef TWO_EDGE_CONNECTED_COMPONENTS_HPP
#define TWO_EDGE_CONNECTED_COMPONENTS_HPP

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

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

  public:
	using Arc = UndirectedCSR::Arc;
	int n;
	std::vector<std::pair<int, int>> edges;
	std::vector<int> component, bridges;
	explicit TwoEdgeConnectedComponents(int n = 0) : n(n) {
		assert(0 <= n && n < std::numeric_limits<int>::max());
	}
	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() {
		built_ = false;
		UndirectedCSR graph(n, edges);
		std::vector<int> ord(n, -1), low(n);
		std::vector<Frame> stack;
		stack.reserve(n);
		vertices_.resize(n), component.resize(n), bridges.clear();
		bridges.reserve(std::min(edges.size(), std::size_t(n ? n - 1 : 0)));
		boundaries_.reserve(std::size_t(n) + 1);
		boundaries_.clear(), boundaries_.push_back(n);
		int timer = 0, top = 0, end = n;
		for (int root = 0; root < n; ++root) if (ord[root] == -1) {
			ord[root] = low[root] = timer++;
			vertices_[top++] = root;
			stack.push_back({root, -1, graph.start[root]});
			while (!stack.empty()) {
				auto &frame = stack.back();
				int v = frame.v;
				if (frame.next == graph.start[v + 1]) {
					int parent = frame.parent;
					stack.pop_back();
					if (low[v] == ord[v]) {
						int id = static_cast<int>(boundaries_.size()) - 1, u;
						do {
							u = vertices_[--top];
							component[u] = id, vertices_[--end] = u;
						} while (u != v);
						boundaries_.push_back(end);
						if (parent != -1) bridges.push_back(parent);
					} else {
						int p = stack.back().v;
						low[p] = std::min(low[p], low[v]);
					}
					continue;
				}
				auto [to, id] = graph.adj[frame.next++];
				if (id == frame.parent) continue;
				if (ord[to] != -1) low[v] = std::min(low[v], ord[to]);
				else {
					ord[to] = low[to] = timer++;
					vertices_[top++] = to;
					stack.push_back({to, id, graph.start[to]});
				}
			}
		}
		built_ = true;
	}
	int component_count() const { assert(built_); return static_cast<int>(boundaries_.size()) - 1; }
	bool same(int u, int v) const { check_(u), check_(v); return component[u] == component[v]; }
	bool is_bridge(int id) const {
		assert(built_ && 0 <= id && id < static_cast<int>(edges.size()));
		auto [u, v] = edges[id];
		return component[u] != component[v];
	}
	std::span<const int> group(int id) const {
		assert(built_ && 0 <= id && id < component_count());
		return {vertices_.data() + boundaries_[id + 1], std::size_t(boundaries_[id] - boundaries_[id + 1])};
	}
	std::vector<std::vector<int>> groups() const {
		std::vector<std::vector<int>> result(component_count());
		for (int i = 0; i < component_count(); ++i) {
			auto members = group(i);
			result[i].assign(members.begin(), members.end());
		}
		return result;
	}
	std::vector<std::vector<Arc>> forest() const {
		std::vector<std::vector<Arc>> result(component_count());
		for (int id : bridges) {
			auto [u, v] = edges[id];
			int a = component[u], b = component[v];
			result[a].push_back({b, id}), result[b].push_back({a, id});
		}
		return result;
	}
};

#endif

Back to top page