Functional Graph

graph/functional_graph.hpp · GitHub で見る

共通ページ

各頂点から出る辺がちょうど 1 本の有向グラフを、閉路とその閉路へ流れ込む木に分解します。閉路の列挙、閉路までの距離、k 回移動した先、到達距離などを求められます。自己ループと複数の連結成分に対応します。

#include "lib/graph/functional_graph.hpp"

std::vector<int> to{1, 2, 0, 1, 3, 3, 6};
FunctionalGraph graph(to);
int count = graph.cycle_count();        // 2
int entry = graph.entry[4];             // 1: 最初に到達する閉路上の頂点
int depth = graph.depth[4];             // 2: 4 -> 3 -> 1
int next = graph.jump(4, 3);            // 2: 4 -> 3 -> 1 -> 2
int distance = graph.dist(4, 2);        // 3
int unreachable = graph.dist(2, 4);     // -1
int reachable = graph.reachable_count(4); // 5: 自身を含む到達可能な頂点数
int merge = graph.lca(4, 5);            // 3
auto cycle = graph.cycle(graph.cycle_id[4]); // 0, 1, 2
auto forest = graph.forest();          // 閉路上の辺を除いた無向森

入力は std::vector<int> の移動先配列です。頂点番号は 0 始まりで、v -> to[v] を表します。頂点数は INT_MAX 以下とし、全ての to[v] を [0,n) に入れてください。行き止まりを表す -1 は扱いません。空配列にも対応し、既定構築も空の状態です。

入力を変更せず、構築結果は入力を参照しません。FunctionalGraph(std::move(to)) で移動先配列を渡せば、その配列の所有権を移せます。コピーして独立に保持することもできます。

操作	内容・返り値	計算量
FunctionalGraph(to)	移動先配列から構築	\(O(n)\)
build(to)	指定した配列で構築し直す	\(O(n)\)
size() / empty()	頂点数／空かどうか	\(O(1)\)
cycle_count()	閉路の個数。弱連結成分の個数に等しい	\(O(1)\)
cycle(id)	閉路を辺の向きに並べた std::span<const int>	\(O(1)\)
cycle_length(v)	v が到達する閉路の長さ	\(O(1)\)
on_cycle(v)	v 自身が閉路上か	\(O(1)\)
same_component(u,v)	辺の向きを無視すると同じ連結成分か	\(O(1)\)
reachable_count(v)	自身を含む到達可能な頂点数	\(O(1)\)
jump(v,k)	v から辺を k 回たどった先	\(O(\log n)\)
dist(u,v)	u から v へ移動する最小回数。到達不能なら -1	\(O(1)\)
lca(u,v)	閉路上の辺を除いた逆向きの木での LCA。異なる木なら -1	\(O(\log n)\)
subtree(v)	逆向きの木の部分木が占める半開区間 [l,r)	\(O(1)\)
vertex_at(position)	subtree と同じ順序における頂点番号	\(O(1)\)
forest()	閉路上の辺を全て除いた vector<vector<int>> の無向森	\(O(n)\)

cycle(id) の ID は [0,cycle_count()) です。閉路の最後の頂点から最初の頂点へも辺があります。自己ループは長さ 1 の閉路です。戻り値は本体の配列を参照するので、本体の再構築・代入・破棄後は使わないでください。

jump の k は std::uint64_t で、0 から UINT64_MAX まで指定できます。負の整数は渡さないでください。k が大きくても、閉路に到達した後は長さで剰余を取って O(1) で処理します。閉路に入る前だけ HLD の経路をたどります。

same_component(u,v) が真でも、u から v へ到達できるとは限りません。到達できるかは dist(u,v) != -1 で判定できます。

公開配列	内容
to[v]	元の辺の移動先
cycle_id[v]	到達する閉路の ID。連結成分の ID としても使える
cycle_position[v]	閉路内の位置。閉路上でなければ -1
entry[v]	最初に到達する閉路上の頂点。閉路上では自身
depth[v]	閉路に到達するまでの辺数。閉路上では 0
parent[v]	閉路上では -1、それ以外では to[v]
subtree_size[v]	閉路上の辺を除いた逆向きの木での、自身を含む部分木サイズ

公開配列は構築結果を参照するためのものです。辺を変える場合は build を呼び直してください。

閉路上の辺を除くと、閉路上の各頂点を根とする森になります。元の辺は子から親へ向くので、逆向きに見て通常の根付き木として扱います。lca(u,v) は entry[u] == entry[v] の場合だけその木の LCA を返します。同じ閉路へ到達しても、最初に到達する閉路上の頂点が異なれば -1 です。

subtree(v) の区間は元の頂点番号の区間ではありません。vertex_at(l) が v 自身で、[l,r) の各位置に対応する頂点がその子孫です。r-l == subtree_size[v] が成り立ちます。Fenwick Tree やセグメント木と組み合わせて、流れ込む頂点への部分木クエリを処理できます。forest() はこの森の各辺を両方向に入れた隣接リストを返します。閉路の長さが 2 の場合も、両方向の閉路辺を両方除きます。

入次数 0 の頂点を取り除き、残った閉路を列挙します。取り除いた順序から部分木サイズと heavy な子を求め、逆順に閉路の情報を伝播して HLD の順序を付けます。再帰・ダブリング表・逆向き隣接リストを使わずに前処理します。

頂点数を \(n\) として、構築・build は \(O(n)\) 時間・空間です。jump・lca は \(O(\log n)\) 時間、forest() は \(O(n)\) 時間・返す隣接リストに \(O(n)\) 空間、それ以外のクエリは \(O(1)\) 時間です。

検証コード

• test/functional_graph_jump.test.cpp

コード

#ifndef FUNCTIONAL_GRAPH_HPP
#define FUNCTIONAL_GRAPH_HPP

#include <algorithm>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <limits>
#include <span>
#include <utility>
#include <vector>

class FunctionalGraph {
	std::vector<int> head_, in_, order_, cycle_vertices_, cycle_offsets_;
	void check([[maybe_unused]] int v) const { assert(0 <= v && v < size()); }

  public:
	std::vector<int> to, parent, cycle_id, cycle_position, entry, depth, subtree_size;
	FunctionalGraph() = default;
	explicit FunctionalGraph(std::vector<int> next) { build(std::move(next)); }
	void build(std::vector<int> next) {
		assert(next.size() <= std::size_t(std::numeric_limits<int>::max()));
		const int n = static_cast<int>(next.size());
		for ([[maybe_unused]] int v : next) assert(0 <= v && v < n);
		to = std::move(next);
		parent.resize(n);
		cycle_id.assign(n, -1);
		cycle_position.assign(n, -1);
		entry.resize(n);
		depth.assign(n, 0);
		subtree_size.assign(n, 1);
		head_.resize(n);
		in_.resize(n);
		order_.resize(n);
		cycle_vertices_.clear();
		cycle_offsets_.clear();
		std::vector<int> indegree(n), heavy(n, -1), peeled;
		peeled.reserve(n);
		for (int v : to) ++indegree[v];
		for (int v = 0; v < n; ++v) if (!indegree[v]) peeled.push_back(v);
		for (std::size_t i = 0; i < peeled.size(); ++i) {
			int v = peeled[i], p = to[v];
			parent[v] = p;
			subtree_size[p] += subtree_size[v];
			if (heavy[p] == -1 || subtree_size[heavy[p]] < subtree_size[v]) heavy[p] = v;
			if (!--indegree[p]) peeled.push_back(p);
		}
		cycle_vertices_.reserve(std::size_t(n) - peeled.size());
		int position = 0;
		for (int v = 0; v < n; ++v) if (indegree[v] && cycle_id[v] == -1) {
			int id = cycle_count(), start = static_cast<int>(cycle_vertices_.size()), u = v;
			cycle_offsets_.push_back(start);
			do {
				cycle_id[u] = id;
				cycle_position[u] = static_cast<int>(cycle_vertices_.size()) - start;
				cycle_vertices_.push_back(u);
				entry[u] = u;
				parent[u] = -1;
				head_[u] = u;
				in_[u] = position;
				position += subtree_size[u];
				order_[u] = position;
				u = to[u];
			} while (u != v);
		}
		assert(position == n);
		for (auto it = peeled.rbegin(); it != peeled.rend(); ++it) {
			int v = *it, p = to[v];
			cycle_id[v] = cycle_id[p];
			entry[v] = entry[p];
			depth[v] = depth[p] + 1;
			if (heavy[p] == v) in_[v] = in_[p] + 1, head_[v] = head_[p];
			else in_[v] = order_[p] -= subtree_size[v], head_[v] = v;
			order_[v] = in_[v] + subtree_size[v];
		}
		for (int v = 0; v < n; ++v) order_[in_[v]] = v;
	}
	int size() const { return static_cast<int>(to.size()); }
	bool empty() const { return to.empty(); }
	int cycle_count() const { return static_cast<int>(cycle_offsets_.size()); }
	std::span<const int> cycle(int id) const {
		assert(0 <= id && id < cycle_count());
		int start = cycle_offsets_[id];
		int end = id + 1 < cycle_count() ? cycle_offsets_[id + 1] : static_cast<int>(cycle_vertices_.size());
		return std::span<const int>(cycle_vertices_).subspan(start, end - start);
	}
	int cycle_length(int v) const {
		check(v);
		return static_cast<int>(cycle(cycle_id[v]).size());
	}
	bool on_cycle(int v) const {
		check(v);
		return depth[v] == 0;
	}
	bool same_component(int u, int v) const {
		check(u), check(v);
		return cycle_id[u] == cycle_id[v];
	}
	int reachable_count(int v) const {
		check(v);
		return depth[v] + cycle_length(v);
	}
	int jump(int v, std::uint64_t k) const {
		check(v);
		if (k < std::uint64_t(depth[v])) {
			int target = depth[v] - static_cast<int>(k);
			while (depth[head_[v]] > target) v = to[head_[v]];
			return order_[in_[v] - (depth[v] - target)];
		}
		k -= depth[v];
		v = entry[v];
		auto vertices = cycle(cycle_id[v]);
		std::size_t position = cycle_position[v] + k % vertices.size();
		if (position >= vertices.size()) position -= vertices.size();
		return vertices[position];
	}
	int dist(int u, int v) const {
		if (!same_component(u, v)) return -1;
		if (depth[v]) return in_[v] <= in_[u] && in_[u] < in_[v] + subtree_size[v] ? depth[u] - depth[v] : -1;
		int offset = cycle_position[v] - cycle_position[entry[u]];
		if (offset < 0) offset += cycle_length(v);
		return depth[u] + offset;
	}
	int lca(int u, int v) const {
		check(u), check(v);
		if (entry[u] != entry[v]) return -1;
		while (head_[u] != head_[v]) {
			if (depth[head_[u]] < depth[head_[v]]) std::swap(u, v);
			u = to[head_[u]];
		}
		return depth[u] < depth[v] ? u : v;
	}
	std::pair<int, int> subtree(int v) const {
		check(v);
		return {in_[v], in_[v] + subtree_size[v]};
	}
	int vertex_at(int position) const {
		assert(0 <= position && position < size());
		return order_[position];
	}
	std::vector<std::vector<int>> forest() const {
		std::vector<std::vector<int>> result(size());
		for (int v = 0; v < size(); ++v) if (parent[v] != -1) {
			result[v].push_back(parent[v]);
			result[parent[v]].push_back(v);
		}
		return result;
	}
};

#endif

Back to top page