potentialized_union_find

クラス · ポテンシャル付き素集合データ構造（可換・非可換どちらの群でも可）

template <internal::group G>
struct potentialized_union_find;

概要

ポテンシャル付き素集合データ構造（可換・非可換どちらの群でも可）

各要素 $x$ に群 G の隠れた値 $a_x$ が割り当てられているとし、 $a_x^{-1} \cdot a_y$ という相対関係（ポテンシャル差）を管理する。 G が * と .inv() を持てば乗法群（非可換も可・単位元は G()）、 + と単項 - を持てば加法可換群（単位元は G(0)）として自動的に扱う。

テンプレートパラメータ

名前	説明
`G`	群を表す型

計算量

群演算を $O(1)$ として、代表・差・併合は償却 $O(\alpha(n))$

構築・破棄

名前	説明	計算量
`(constructor)`	(1) 空の Union-Find を作る (2) `n` 個の単集合を単位ポテンシャルで作る	(1) $O(1)$ (2) $O(n)$

メンバ関数

名前	説明	計算量
`root`	x の根を返す（経路圧縮あり）。同時に _pot[x] を根に対する相対値へ更新する。	群演算を $O(1)$ として償却 $O(\alpha(n))$
`get_root`	`root(x)` の別名	群演算を $O(1)$ として償却 $O(\alpha(n))$
`is_root`	`x` が集合の代表なら true を返す	$O(1)$
`potential`	根に対する相対ポテンシャル $a_{\mathrm{root}}^{-1} \cdot a_x$ を返す。	群演算を $O(1)$ として償却 $O(\alpha(n))$
`get_potential`	`potential(x)` の別名	群演算を $O(1)$ として償却 $O(\alpha(n))$
`same`	`x`, `y` が同じ集合なら true を返す	群演算を $O(1)$ として償却 $O(\alpha(n))$
`is_same`	`same(x, y)` の別名	群演算を $O(1)$ として償却 $O(\alpha(n))$
`size`	`x` が属する集合の要素数を返す	群演算を $O(1)$ として償却 $O(\alpha(n))$
`get_size`	`size(x)` の別名	群演算を $O(1)$ として償却 $O(\alpha(n))$
`diff`	$a_x^{-1} \cdot a_y$ を返す（`x`, `y` は同一集合に属していること）。	群演算を $O(1)$ として償却 $O(\alpha(n))$
`get_diff`	`diff(x, y)` の別名	群演算を $O(1)$ として償却 $O(\alpha(n))$
`unite`	関係 $a_x^{-1} \cdot a_y = w$ を追加する。	群演算を $O(1)$ として償却 $O(\alpha(n))$
`valid`	関係 $a_x^{-1} \cdot a_y = w$ が既存の情報と整合するか確認する。	群演算を $O(1)$ として償却 $O(\alpha(n))$

メンバの詳細

(constructor)

// (1)
potentialized_union_find() = default;

// (2)
explicit potentialized_union_find(int n);

(1) 空の Union-Find を作る

計算量: $O(1)$

(2) n 個の単集合を単位ポテンシャルで作る

計算量: $O(n)$

unite

bool unite(int x, int y, const G &w);

関係 $a_x^{-1} \cdot a_y = w$ を追加する。

戻り値: 集合が新たに併合されたら true、既に同一集合なら false。
計算量: 群演算を $O(1)$ として償却 $O(\alpha(n))$
備考: 戻り値が false でも矛盾検出はしない。整合性確認は valid を使う。

valid

bool valid(int x, int y, const G &w);

関係 $a_x^{-1} \cdot a_y = w$ が既存の情報と整合するか確認する。

別集合なら併合して true、同一集合なら現在の差と一致するかを返す。

計算量: 群演算を $O(1)$ として償却 $O(\alpha(n))$