undo_union_find
クラス · Undo可能Union-Find
struct undo_union_find;
概要
Undo可能Union-Find
経路圧縮を行わず、union by sizeと変更履歴で状態を巻き戻す。
計算量
root・same・unite・sizeは $O(\log n)$、undoは $O(1)$、rollbackは取り消す併合回数に比例
構築・破棄
| 名前 | 説明 | 計算量 |
|---|---|---|
(constructor) |
(1) 空の Union-Find を作る (2) n 個の単集合を作る |
(1) $O(1)$ (2) $O(n)$ |
メンバ関数
| 名前 | 説明 | 計算量 |
|---|---|---|
root |
x の代表を返す |
$O(\log n)$ |
get_root |
root(k) の別名 |
$O(\log n)$ |
is_root |
k が集合の代表なら true を返す |
$O(1)$ |
same |
x, y が同じ集合なら true を返す |
$O(\log n)$ |
is_same |
same(x, y) の別名 |
$O(\log n)$ |
size |
k が属する集合の要素数を返す |
$O(\log n)$ |
get_size |
size(k) の別名 |
$O(\log n)$ |
unite |
x, y の集合を併合し、操作履歴を追加する |
$O(\log n)$ |
undo |
最後の unite 1 回分を取り消す |
$O(1)$ |
snapshot |
現在の状態を表す履歴位置を返す | $O(1)$ |
rollback |
履歴位置 x の状態まで併合を取り消す |
取り消す unite の回数に比例 |
メンバの詳細
(constructor)
// (1)
undo_union_find();
// (2)
undo_union_find(int _n);
(1) 空の Union-Find を作る
- 計算量: $O(1)$
(2) n 個の単集合を作る
- 計算量: $O(n)$
unite
bool unite(int x, int y);
x, y の集合を併合し、操作履歴を追加する
- 戻り値: 新たに併合したなら true
- 計算量: $O(\log n)$