Low-Link

graph/low_link.hpp · GitHub で見る

共通ページ

#include "lib/graph/low_link.hpp"

LowLink graph(3);
int id = graph.add_edge(0, 1);
graph.add_edge(1, 2);
graph.build();
bool bridge = graph.is_bridge(id); // true
auto vertices = graph.articulation; // {1}

操作	内容・返り値	計算量
LowLink(n)	頂点数を指定	\(O(1)\)
add_edge(u,v)	無向辺を追加し、辺 ID を返す	償却 \(O(1)\)
build()	関節点・橋を計算。辺の追加後は再実行	\(O(n+m)\)
is_bridge(id)	辺 ID が橋か	\(O(1)\)
articulation / bridges	関節点の一覧／橋の辺 ID の一覧	\(O(1)\)
ord[v] / low[v]	DFS の訪問順／後退辺を使って到達できる最小の訪問順	\(O(1)\)
n / edges[id]	全頂点数／辺の両端	\(O(1)\)

無向グラフを扱います。頂点番号は 0 始まり、add_edge(u, v) は辺 ID を返します。

build() 後に articulation から関節点、bridges から橋の辺 ID、edges[id] から辺の両端を取得できます。is_bridge(id) で橋か判定できます。辺を追加した後は build() を再実行します。

\(n\) 頂点・\(m\) 辺として、build() は時間・空間ともに \(O(n+m)\)、add_edge は償却 \(O(1)\)、is_bridge は \(O(1)\) です。

依存ライブラリ

• 無向グラフの CSR

検証コード

• test/low_link_articulation.test.cpp
• test/low_link_bridge.test.cpp

コード

#ifndef LOW_LINK_HPP
#define LOW_LINK_HPP

#include "../components/undirected_csr.hpp"
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <limits>
#include <memory>
#include <utility>
#include <vector>

struct LowLink {
	using Arc = UndirectedCSR::Arc;
	struct Frame {
		int v, parent, next;
	};
	int n;
	std::vector<std::pair<int, int>> edges;
	std::vector<int> ord, low, articulation, bridges;
	explicit LowLink(int n) : n(n) { assert(n >= 0); }
	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));
		int id = static_cast<int>(edges.size());
		edges.emplace_back(u, v);
		return id;
	}
	void build() {
		assert(n >= 0 && edges.size() <= std::size_t(std::numeric_limits<int>::max() / 2));
		UndirectedCSR graph(n, edges);
		const auto &start = graph.start;
		const auto &adj = graph.adj;
		ord.assign(n, -1);
		low.assign(n, -1);
		articulation.clear();
		bridges.clear();
		std::vector<std::uint8_t> cut(n);
		std::vector<Frame> stack;
		stack.reserve(n);
		int timer = 0;
		for (int root = 0; root < n; ++root) {
			if (ord[root] != -1) continue;
			int children = 0;
			ord[root] = low[root] = timer++;
			stack.push_back({root, -1, start[root]});
			while (!stack.empty()) {
				auto &f = stack.back();
				int v = f.v;
				if (f.next == start[v + 1]) {
					int id = f.parent;
					stack.pop_back();
					if (stack.empty()) cut[v] = children > 1;
					else {
						int p = stack.back().v;
						low[p] = std::min(low[p], low[v]);
						if (ord[p] < low[v]) bridges.push_back(id);
						if (p != root && ord[p] <= low[v]) cut[p] = 1;
					}
					continue;
				}
				auto [to, id] = adj[f.next++];
				if (id == f.parent) continue;
				if (ord[to] != -1) {
					low[v] = std::min(low[v], ord[to]);
					continue;
				}
				children += v == root;
				ord[to] = low[to] = timer++;
				stack.push_back({to, id, start[to]});
			}
		}
		for (int v = 0; v < n; ++v)
			if (cut[v]) articulation.push_back(v);
	}
	bool is_bridge(int id) const {
		assert(0 <= id && id < static_cast<int>(edges.size()) && static_cast<int>(ord.size()) == n);
		auto [u, v] = edges[id];
		if (ord[u] > ord[v]) std::swap(u, v);
		return ord[u] < low[v];
	}
};

#endif

Back to top page