PersistentUnionFind
クラス · 各バージョンを保持する完全永続 Union-Find
struct PersistentUnionFind;
概要
各バージョンを保持する完全永続 Union-Find
併合は元の状態を変更せず、新しい Union-Find を返す。
計算量
- 代表・連結判定・サイズ取得・併合は $O(\log^2 n)$
構築・破棄
| 名前 | 説明 | 計算量 |
|---|---|---|
(constructor) |
(1) 空の Union-Find を作る (2) 永続配列 _data を内部状態とする Union-Find を作る(3) n 個の単集合を作る |
(1) $O(1)$ (2) $O(1)$ (3) $O(n\log n)$ |
メンバ関数
| 名前 | 説明 | 計算量 |
|---|---|---|
root |
x の代表を返す |
$O(\log^2 n)$ |
get_root |
root(x) の別名 |
$O(\log^2 n)$ |
is_root |
x が集合の代表なら true を返す |
$O(\log n)$ |
unite |
x, y を併合した新しいバージョンを返す |
$O(\log^2 n)$ |
size |
x が属する集合の要素数を返す |
$O(\log^2 n)$ |
get_size |
size(x) の別名 |
$O(\log^2 n)$ |
same |
x, y が同じ集合なら true を返す |
$O(\log^2 n)$ |
is_same |
same(x, y) の別名 |
$O(\log^2 n)$ |
メンバの詳細
(constructor)
// (1)
constexpr PersistentUnionFind();
// (2)
PersistentUnionFind(const PersistentArray<int> &_data);
// (3)
PersistentUnionFind(int n);
(1) 空の Union-Find を作る
- 計算量: $O(1)$
(2) 永続配列 _data を内部状態とする Union-Find を作る
- 計算量: $O(1)$
(3) n 個の単集合を作る
- 計算量: $O(n\log n)$