差分
このページの2つのバージョン間の差分を表示します。
| 両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン | ||
| programming_algorithm:data_structure:union_find_tree [2020/05/07] – [実装] ikatakos | programming_algorithm:data_structure:union_find_tree [2023/05/26] (現在) – [ポテンシャル付きUnion-Find] ikatakos | ||
|---|---|---|---|
| 行 3: | 行 3: | ||
| * [[wpjp> | * [[wpjp> | ||
| - | * 要素が $n$ 個あり、各要素は互いに素なグループに1つだけ属する | + | * 要素が $N$ 個あり、各要素は互いに素なグループに1つだけ属する |
| - | * 例: 生徒は必ず何かのクラブ活動に入り、兼部は認められていない | + | * 例: 生徒は必ず何かのクラブ活動に1つだけ入り、兼部は認められていない |
| * グループは統合される可能性があるが、分割はされない | * グループは統合される可能性があるが、分割はされない | ||
| という前提で、 | という前提で、 | ||
| - | * ${\rm Union}(x, y)$: 要素xの属するグループと、yの属するグループを統合する | + | * '' |
| - | * ${\rm Find}(x, y)$: 要素xとyが同じグループに属するか調べる | + | * '' |
| という2つのクエリを効率的に処理するのが、Union-Find木 | という2つのクエリを効率的に処理するのが、Union-Find木 | ||
| 行 17: | 行 17: | ||
| * [[http:// | * [[http:// | ||
| * [[http:// | * [[http:// | ||
| + | |||
| + | Disjoint Set Union、略してDSUともいう。 | ||
| =====アルゴリズム===== | =====アルゴリズム===== | ||
| 行 26: | 行 28: | ||
| < | < | ||
| - | １ ４ ８ ←代表 | + | １ ４ ８ ←1,4,8が代表 |
| ↗↑ | ↗↑ | ||
| - | ２ ５ ６ | + | ２ ５ ６ |
| | | ||
| | | ||
| </ | </ | ||
| - | | + | これをもとに、先ほどの2つの操作を言い換えると、以下のようになる。 |
| - | * ${\rm Find}(x, y)$は、xとyから親を辿って同じ代表に行き着くか調べる | + | |
| + | | ||
| + | * '' | ||
| + | |||
| + | また、そのために以下の操作も持つ。 | ||
| + | |||
| + | * '' | ||
| + | |||
| + | これを根を見つける(Find)と捉え、2つの操作を合わせてUnion-Findとなる。 | ||
| - | ====高速化の工夫==== | + | ==== 高速化の工夫 ==== |
| * 木の階層を低く保たないと、代表を見つける処理に時間がかかる | * 木の階層を低く保たないと、代表を見つける処理に時間がかかる | ||
| 行 42: | 行 52: | ||
| * おそい例では、４からだと、４→３→２→１と3回辿らないと代表に着かない | * おそい例では、４からだと、４→３→２→１と3回辿らないと代表に着かない | ||
| * できるだけ、はやい例のような状態を保ちたい | * できるだけ、はやい例のような状態を保ちたい | ||
| + | |||
| < | < | ||
| ◎はやい | ◎はやい | ||
| 行 54: | 行 65: | ||
| ===経路圧縮=== | ===経路圧縮=== | ||
| + | |||
| * 一度調べた経路上にある要素は、全て親を代表に書き換える | * 一度調べた経路上にある要素は、全て親を代表に書き換える | ||
| - | * おそい例において、４→３→２→１と調べて１が代表だとわかったら、２～４の親を１に書き換える | + | * おそい例において、一度 '' |
| ===ランク=== | ===ランク=== | ||
| + | |||
| * 木の最大深さ（ランク）を記録しておく | * 木の最大深さ（ランク）を記録しておく | ||
| - | * Union時、ランクの低い方のグループを、高い方のグループにつなぐ | + | * '' |
| * 互いのランクが等しい場合を除き、ランクが高くならずに済む（等しい場合のみ1増える） | * 互いのランクが等しい場合を除き、ランクが高くならずに済む（等しい場合のみ1増える） | ||
| < | < | ||
| - | この2つをUnionする場合| こうすると | + | この2つをuniteする場合| こうすると |
| | | ||
| | | ||
| 行 76: | 行 89: | ||
| </ | </ | ||
| - | ランクは深さでなく、要素数で考えることもある | + | ==== 計算量 ==== |
| + | |||
| + | 上記の2つの改善を行って、'' | ||
| + | |||
| + | これはいずれもならし計算量で、何回もやると平均がこの値に近づいていく。 | ||
| + | |||
| + | ただし $\alpha(N)$ はアッカーマン関数 $\rm{Ack}(N, | ||
| + | |||
| + | * [[https:// | ||
| - | * 例: 要素数100, | ||
| - | * AにBを繋ぐとBの5個の要素の深さが1ずつ増え、最大深さは5 | ||
| - | * BにAを繋ぐとAの100個の要素の深さが1ずつ増え、最大深さは4 | ||
| - | * 局所的に最大深さが深くなろうが、100個の要素の深さが1ずつ増える方が効率悪くない？という考え方か | ||
| - | * A.V.Aho, John E. Hopcroft, Jeffrey D. Ulman, 『データ構造とアルゴリズム』, | ||
| =====実装===== | =====実装===== | ||
| - | * 要素数 $n$ の配列'' | + | * 要素数 $N$ の配列'' |
| * ${\rm table}[x]$ が負ならば、$x$ は代表。絶対値はランクを示す | * ${\rm table}[x]$ が負ならば、$x$ は代表。絶対値はランクを示す | ||
| * ${\rm table}[x]$ が非負ならば、$x$ は代表でない。値は $x$ の親を示す | * ${\rm table}[x]$ が非負ならば、$x$ は代表でない。値は $x$ の親を示す | ||
| - | * 最初は、$n$個の要素が別々の$n$個のグループに所属している状態 | + | * 最初は、$N$ 個の要素が別々の $N$ 個のグループに所属している状態 |
| - | * '' | + | * '' |
| * ついでに経路圧縮を行う | * ついでに経路圧縮を行う | ||
| - | < | + | < |
| + | |||
| + | '' | ||
| <sxh python> | <sxh python> | ||
| 行 104: | 行 123: | ||
| self.table = [-1] * n | self.table = [-1] * n | ||
| - | def _root(self, x): | + | def root(self, x): |
| stack = [] | stack = [] | ||
| tbl = self.table | tbl = self.table | ||
| 行 114: | 行 133: | ||
| return x | return x | ||
| - | def find(self, x, y): | + | def is_same(self, x, y): |
| - | return self._root(x) == self._root(y) | + | return self.root(x) == self.root(y) |
| - | def union(self, x, y): | + | def unite(self, x, y): |
| - | r1 = self._root(x) | + | r1 = self.root(x) |
| - | r2 = self._root(y) | + | r2 = self.root(y) |
| if r1 == r2: | if r1 == r2: | ||
| return | return | ||
| 行 135: | 行 154: | ||
| if __name__ == ' | if __name__ == ' | ||
| ins = UnionFind(4) | ins = UnionFind(4) | ||
| - | ins.union(0, 1) | + | ins.unite(0, 1) |
| - | ins.union(2, 3) | + | ins.unite(2, 3) |
| - | print(ins.find(0, 3)) # False | + | print(ins.is_same(0, 3)) # False |
| - | ins.union(1, 2) | + | ins.unite(1, 2) |
| - | print(ins.find(0, 3)) # True | + | print(ins.is_same(0, 3)) # True |
| </ | </ | ||
| - | 統合時、どちらを根にするかの基準をグループの深さで無く「要素数」とした実装。unionの部分が少し変化。 | + | ===== 亜種 ===== |
| + | |||
| + | ==== ランクを要素数とする | ||
| + | |||
| + | ランクは木の深さでなく、要素数で考えることもある。 | ||
| + | |||
| + | * 例: 要素数100, | ||
| + | * AにBを繋ぐとBの5個の要素の深さが1ずつ増え、最大深さは5 | ||
| + | * BにAを繋ぐとAの100個の要素の深さが1ずつ増え、最大深さは4 | ||
| + | * 局所的に最大深さが深くなろうが、100個の要素の深さが1ずつ増える方が効率悪くない？という考え方か | ||
| + | * A.V.Aho, John E. Hopcroft, Jeffrey D. Ulman, 『データ構造とアルゴリズム』, | ||
| + | |||
| + | 実際、どちらを選んでも計算量は変わらない（経路圧縮を行う場合で $O(\alpha(N))$、行わない場合で $O(\log{N})$）し、速度は体感できるほど変わらない。 | ||
| + | |||
| + | * [[https:// | ||
| + | |||
| + | 木の深さってあまり使い道が無いが、「$x$ が含まれるグループの要素数」は任意の時点で取得できると嬉しい場合はある。\\ | ||
| + | よって、ランクは要素数としておいた方が、何かと便利かも知れない。 | ||
| + | |||
| + | |||
| + | === 実装 | ||
| + | |||
| + | '' | ||
| + | |||
| + | ++++ Python3 | | ||
| <sxh python> | <sxh python> | ||
| 行 151: | 行 194: | ||
| self.table = [-1] * n | self.table = [-1] * n | ||
| - | def _root(self, x): | + | def root(self, x): |
| stack = [] | stack = [] | ||
| tbl = self.table | tbl = self.table | ||
| 行 161: | 行 204: | ||
| return x | return x | ||
| - | def find(self, x, y): | + | def is_same(self, x, y): |
| - | return self._root(x) == self._root(y) | + | return self.root(x) == self.root(y) |
| - | def union(self, x, y): | + | def unite(self, x, y): |
| - | r1 = self._root(x) | + | r1 = self.root(x) |
| - | r2 = self._root(y) | + | r2 = self.root(y) |
| if r1 == r2: | if r1 == r2: | ||
| return | return | ||
| 行 177: | 行 220: | ||
| self.table[r1] = r2 | self.table[r1] = r2 | ||
| self.table[r2] += d1 | self.table[r2] += d1 | ||
| + | |||
| + | def get_size(self, | ||
| + | return -self.table[self.root(x)] | ||
| </ | </ | ||
| + | |||
| + | ++++ | ||
| + | |||
| + | |||
| + | ==== グループの要素も保持 ==== | ||
| + | |||
| + | 上記の例では、グループの要素数はわかっても、具体的に現時点でのグループにはどの要素があるのか、というのはわからない。 | ||
| + | |||
| + | グループの要素も管理したい場合、tableとは別にもう1つグループを管理する配列も用意して、実際に統合していく。\\ | ||
| + | '' | ||
| + | |||
| + | * $x$ が含まれるグループの要素を得たいときは、配列で $x$ の根の位置を参照する | ||
| + | * いったん根じゃなくなった要素はもう参照されないので、更新しなくてよい | ||
| + | * '' | ||
| + | * こうするだけで何もしない場合と比較して統合にかかるならし計算量が $O(N)$ から $O(\log{N})$ へ落とされる | ||
| + | * [[http:// | ||
| + | |||
| + | === 実装 === | ||
| + | |||
| + | ++++ Python3 | | ||
| + | |||
| + | <sxh python> | ||
| + | class UnionFindWithGrouping: | ||
| + | def __init__(self, | ||
| + | self.table = [-1] * n | ||
| + | self.group = [{i} for i in range(n)] | ||
| + | |||
| + | def root(self, x): | ||
| + | stack = [] | ||
| + | tbl = self.table | ||
| + | while tbl[x] >= 0: | ||
| + | stack.append(x) | ||
| + | x = tbl[x] | ||
| + | for y in stack: | ||
| + | tbl[y] = x | ||
| + | return x | ||
| + | |||
| + | def is_same(self, | ||
| + | return self.root(x) == self.root(y) | ||
| + | |||
| + | def unite(self, x, y): | ||
| + | r1 = self.root(x) | ||
| + | r2 = self.root(y) | ||
| + | if r1 == r2: | ||
| + | return | ||
| + | |||
| + | d1 = self.table[r1] | ||
| + | d2 = self.table[r2] | ||
| + | if d1 <= d2: | ||
| + | self.table[r2] = r1 | ||
| + | self.table[r1] += d2 | ||
| + | self.group[r1].update(self.group[r2]) | ||
| + | else: | ||
| + | self.table[r1] = r2 | ||
| + | self.table[r2] += d1 | ||
| + | self.group[r2].update(self.group[r1]) | ||
| + | |||
| + | def get_size(self, | ||
| + | return -self.table[self.root(x)] | ||
| + | |||
| + | def get_group(self, | ||
| + | return self.group[self.root(x)] | ||
| + | </ | ||
| + | |||
| + | ++++ | ||
| + | |||
| + | |||
| + | ==== Rollback付きUnion-Find ==== | ||
| + | |||
| + | Undo付きUnion-Findなどとも呼ばれる。履歴を持ち、直前で結合したグループを戻せる。 | ||
| + | |||
| + | * [[https:// | ||
| + | |||
| + | * '' | ||
| + | * '' | ||
| + | * '' | ||
| + | * '' | ||
| + | |||
| + | 通常のUnion-Findに、rollbackの機能が加わったもの。 | ||
| + | |||
| + | 計算量は $O(\alpha(N))$ から 若干悪化して $O(\log{N})$ となるが、それでも十分高速。 | ||
| + | |||
| + | Union-Findにおいてtableの変更が行われるのは、 | ||
| + | |||
| + | * '' | ||
| + | * '' | ||
| + | * '' | ||
| + | * 一方の '' | ||
| + | * 継続する代表 '' | ||
| + | |||
| + | このうち、経路圧縮をおこなうのは以下の理由からやや難しい。 | ||
| + | |||
| + | * 変更箇所が複数に及ぶ | ||
| + | * '' | ||
| + | |||
| + | 一方、結合時は変更が確実に「'' | ||
| + | |||
| + | 「変更した要素 $x, | ||
| + | |||
| + | |||
| + | === 実装 === | ||
| + | |||
| + | 細かな実装の違いとして、uniteしようとした結果、既に同グループだった場合、履歴に残すかどうかがあるが、 | ||
| + | 有効だったかどうかを呼び出し側が管理しないで済むので、基本的には残した方がよさそう。 | ||
| + | |||
| + | ++++ Python3 | | ||
| + | |||
| + | <sxh python> | ||
| + | class RollbackUnionFind: | ||
| + | """ | ||
| + | 履歴を持ち、直前の操作を（順に）取り消せるUnionFind | ||
| + | """ | ||
| + | |||
| + | def __init__(self, | ||
| + | self.table = [-1] * n | ||
| + | self.history = [] | ||
| + | # (継続リーダー番号1, | ||
| + | # 無効なuniteの場合、被統合リーダー番号を" | ||
| + | |||
| + | def root(self, x: int): | ||
| + | tbl = self.table | ||
| + | while tbl[x] >= 0: | ||
| + | x = tbl[x] | ||
| + | return x | ||
| + | |||
| + | def is_same(self, | ||
| + | return self.root(x) == self.root(y) | ||
| + | |||
| + | def unite(self, x: int, y: int): | ||
| + | r1 = self.root(x) | ||
| + | r2 = self.root(y) | ||
| + | if r1 == r2: | ||
| + | self.history.append((r1, | ||
| + | return False | ||
| + | d1 = self.table[r1] | ||
| + | d2 = self.table[r2] | ||
| + | if d1 <= d2: | ||
| + | self.table[r2] = r1 | ||
| + | self.table[r1] += d2 | ||
| + | self.history.append((r1, | ||
| + | else: | ||
| + | self.table[r1] = r2 | ||
| + | self.table[r2] += d1 | ||
| + | self.history.append((r2, | ||
| + | return True | ||
| + | |||
| + | def rollback(self): | ||
| + | if not self.history: | ||
| + | return False | ||
| + | r1, r2, d1, d2 = self.history.pop() | ||
| + | if r2 == -1: | ||
| + | return False | ||
| + | self.table[r1] = d1 | ||
| + | self.table[r2] = d2 | ||
| + | return True | ||
| + | |||
| + | def get_size(self, | ||
| + | return -self.table[self.root(x)] | ||
| + | |||
| + | </ | ||
| + | |||
| + | ++++ | ||
| + | |||
| + | ==== 部分永続Union-Find ==== | ||
| + | |||
| + | 過去の状態に遡って '' | ||
| + | |||
| + | * '' | ||
| + | * '' | ||
| + | * '' | ||
| + | |||
| + | 更新は最新の状態に対してのみ行える。\\ | ||
| + | （過去の状態からも更新可能にしたものは、「完全永続」という） | ||
| + | |||
| + | * [[https:// | ||
| + | * [[https:// | ||
| + | * [[https:// | ||
| + | |||
| + | 基本的に、クエリが先読みできるなら'' | ||
| + | 通常のUnion-Findで対応可能なので、有用な場面は限られる？ | ||
| + | |||
| + | こちらもRollback Union-Findと同様、経路圧縮は難しいので、計算量はいずれの操作も $O(\log{N})$ となる。 | ||
| + | |||
| + | === 実装 === | ||
| + | |||
| + | 通常のUnionFindではtableは現在値のみを持つところ、「(更新時刻, | ||
| + | |||
| + | 機能(※)の有無により、必要な実装が若干異なる。 | ||
| + | |||
| + | * (※) 根の番号以外の、時刻 $t$ 時点の具体的な何らかの値が取得可能かどうか | ||
| + | * 例: '' | ||
| + | |||
| + | uniteとis_sameしかできない実装を①、get_sizeなども可能な実装を②とする。\\ | ||
| + | ②はわずかに必要メモリが増加する。（追加で $O(クエリ数)$ くらい。まぁ微差） | ||
| + | |||
| + | 通常の初期化: | ||
| + | 値のリスト | ||
| + | | ||
| + | 部分永続①の初期化: | ||
| + | (更新時刻, | ||
| + | |||
| + | 部分永続②の初期化: | ||
| + | (更新時刻, | ||
| + | （他に記録したい値があるならそれもタプルに含める） | ||
| + | | ||
| + | 部分永続①の更新: | ||
| + | | ||
| + | 部分永続②の更新: | ||
| + | |||
| + | 部分永続が通常のUnionFindと異なるのは、主に根を特定する処理 '' | ||
| + | 少しテクニカルな考え方によって、「最終更新時刻と更新値」のみから根が特定できる。 | ||
| + | |||
| + | * 経路圧縮無しUnion-Findにおいて、'' | ||
| + | * '' | ||
| + | * よって、 | ||
| + | * 「現時点の $x$ の最終更新時刻 $\gt t$」なら、$t$ より後に更新されている＝$t$ 時点では根だったことが確定 | ||
| + | * そうでない場合は、最終更新時の値が時刻 $t$ においても続いている | ||
| + | |||
| + | なので、過去の履歴がなくても、最終の更新時刻と更新値があればよい。 | ||
| + | |||
| + | また、部分永続②において '' | ||
| + | |||
| + | * まず $t$ 時点の $x$ の根 $r$ を特定 | ||
| + | * '' | ||
| + | * その時の更新値が求めるもの | ||
| + | |||
| + | |||
| + | ++++ Python3 | | ||
| + | |||
| + | 部分永続②の方。未検証。 | ||
| + | |||
| + | <sxh python> | ||
| + | from bisect import bisect | ||
| + | |||
| + | |||
| + | class PartialPersistentUnionFind: | ||
| + | """ | ||
| + | 時刻 t は、「t番目のuniteクエリ完了時点」を意味する。初期状態は t=0。 | ||
| + | |||
| + | root(x [, t]): 時刻 t の x の根（t 省略時は最新） | ||
| + | find(x, y [, t]): 時刻 t に x と y が同一グループか判定 | ||
| + | unite(x, y): x と y を結合 | ||
| + | get_size(x [, t]): 時刻 t の x の属するグループの要素数 | ||
| + | """ | ||
| + | |||
| + | def __init__(self, | ||
| + | self.t = 0 | ||
| + | self.timetable = [[0] for _ in range(n)] | ||
| + | self.valuetable = [[-1] for _ in range(n)] | ||
| + | |||
| + | def _getvalue(self, | ||
| + | i = bisect(self.timetable[x], | ||
| + | return self.valuetable[x][i] | ||
| + | |||
| + | def root(self, x: int, t: int = -1): | ||
| + | # 更新が行われるのは、その時点の根に対してだけなので、 | ||
| + | # x の最終更新時刻 > t なら、t 時点では確実に x は根。 | ||
| + | # そうでない場合は最終更新時の値の正負で、通常のUnionFindと同様、根か、親を持っているか判別。 | ||
| + | if t == -1: | ||
| + | t = self.t | ||
| + | while self.timetable[x][-1] <= t and self.valuetable[x][-1] >= 0: | ||
| + | x = self.valuetable[x][-1] | ||
| + | return x | ||
| + | |||
| + | def is_same(self, | ||
| + | return self.root(x, | ||
| + | |||
| + | def unite(self, x: int, y: int): | ||
| + | self.t += 1 | ||
| + | r1 = self.root(x, | ||
| + | r2 = self.root(y, | ||
| + | if r1 == r2: | ||
| + | return False | ||
| + | self.timetable[r1].append(self.t) | ||
| + | self.timetable[r2].append(self.t) | ||
| + | d1 = self.valuetable[r1][-1] | ||
| + | d2 = self.valuetable[r2][-1] | ||
| + | if d1 <= d2: | ||
| + | self.valuetable[r1].append(d1 + d2) | ||
| + | self.valuetable[r2].append(r1) | ||
| + | else: | ||
| + | self.valuetable[r1].append(r2) | ||
| + | self.valuetable[r2].append(d1 + d2) | ||
| + | return True | ||
| + | |||
| + | def get_size(self, | ||
| + | if t == -1: | ||
| + | t = self.t | ||
| + | r = self.root(x, | ||
| + | return -self._getvalue(r, | ||
| + | |||
| + | |||
| + | </ | ||
| + | |||
| + | ++++ | ||
| + | |||
| + | |||
| + | ==== 完全永続Union-Find ==== | ||
| + | |||
| + | 全永続～～、あるいは単に永続～～ともいう。英語では Fully Persistent Union-Find。 | ||
| + | |||
| + | * '' | ||
| + | * '' | ||
| + | * '' | ||
| + | |||
| + | 部分永続とは異なり、'' | ||
| + | |||
| + | （$t$ は、時刻というよりバージョン、 | ||
| + | あるいはもっと直接的に「何回目の'' | ||
| + | $t$ は、変更元の $t$ に依らずに回数でナンバリングされていくので、 | ||
| + | $t-1$ や $t+1$ との間に必ずしも関連性があるわけではないが、「時刻」だとあるかのように錯覚しかねないので） | ||
| + | |||
| + | 部分永続Union-Findは、根しか更新対象にならないというUnion-Find特有の性質を上手く使っていたが、 | ||
| + | 完全永続Union-Findは、Union-Find特有と言うよりは、より汎用的な「永続配列」を使って実装する。 | ||
| + | |||
| + | * [[https:// | ||
| + | |||
| + | 元のUnion-Findからの主な変更点は、 | ||
| + | 「状態を保持する配列 table を、永続配列に置き換える」ことくらいなので、 | ||
| + | あまり完全永続Union-Find独自の特長として語ることはないか。 | ||
| + | |||
| + | 一応、Union-Findは一度のuniteで'' | ||
| + | 永続配列を「どこか1箇所書き換えるたびにバージョンが1進む」ようになっていると、 | ||
| + | Union-Findと永続配列でバージョンの進みがずれてきてしまうので、 | ||
| + | 「同時に複数箇所書き換えられる」ようにした永続配列を使えれば少し混乱しにくい。 | ||
| + | |||
| + | === 実装 === | ||
| + | |||
| + | 未検証。 | ||
| + | |||
| + | ++++ Python3 | | ||
| + | |||
| + | <sxh python> | ||
| + | from typing import TypeVar, Generic, List, Optional, Sequence | ||
| + | |||
| + | T = TypeVar(' | ||
| + | |||
| + | |||
| + | class PersistentArrayNode(Generic[T]): | ||
| + | def __init__(self, | ||
| + | self.children: | ||
| + | self.created: | ||
| + | self.value: Optional[T] = value | ||
| + | |||
| + | def copy(self, t: int): | ||
| + | res = PersistentArrayNode(0, | ||
| + | res.children = self.children.copy() | ||
| + | return res | ||
| + | |||
| + | |||
| + | class PersistentArray(Generic[T]): | ||
| + | """ | ||
| + | 永続配列 | ||
| + | """ | ||
| + | |||
| + | def __init__(self, | ||
| + | n = len(array) | ||
| + | log_n = (n - 1).bit_length() | ||
| + | root = PersistentArrayNode(log_n, | ||
| + | |||
| + | self.n = n | ||
| + | self.m = log_n # M分木を構築 | ||
| + | self.roots = [root] | ||
| + | |||
| + | # 初期化 | ||
| + | q = [(0, 1, root)] | ||
| + | m = self.m | ||
| + | while q: | ||
| + | i, d, node = q.pop() | ||
| + | nd = d * m | ||
| + | # children[0] だけはleading-zero問題があるので、別処理 | ||
| + | # （現在の i=xxxx(M進数) としたとき、0xxxx に進むので、そのノード自身の値を持たない） | ||
| + | ci = i + nd | ||
| + | if ci < n: | ||
| + | child = PersistentArrayNode(log_n, | ||
| + | node.children[0] = child | ||
| + | q.append((i, | ||
| + | for j in range(1, m): | ||
| + | ci = i + d * j | ||
| + | if ci < n: | ||
| + | child = PersistentArrayNode(log_n, | ||
| + | node.children[j] = child | ||
| + | q.append((ci, | ||
| + | else: | ||
| + | break | ||
| + | |||
| + | def get_node(self, | ||
| + | # a[i] を示すノードを取得 | ||
| + | # https:// | ||
| + | # （データの持ち方: | ||
| + | node = self.roots[t] | ||
| + | m = self.m | ||
| + | while i > 0: | ||
| + | node = node.children[i % m] | ||
| + | i //= m | ||
| + | return node | ||
| + | |||
| + | def get_value(self, | ||
| + | return self.get_node(i, | ||
| + | |||
| + | def update(self, | ||
| + | t_new = len(self.roots) | ||
| + | node = self.roots[t].copy(t_new) | ||
| + | self.roots.append(node) | ||
| + | m = self.m | ||
| + | |||
| + | while i > 0: | ||
| + | child = node.children[i % m].copy(t_new) | ||
| + | node.children[i % m] = child | ||
| + | node = child | ||
| + | i //= m | ||
| + | |||
| + | node.value = x | ||
| + | |||
| + | return t_new | ||
| + | |||
| + | def update_newest(self, | ||
| + | """ | ||
| + | 最新バージョンに対し、新規バージョンを作らないで更新する。 | ||
| + | 複数箇所を一括に更新することがあり、一括更新の途中状態は不要という場合、 | ||
| + | 最初だけ update し、2番目以降の更新をこちらにすることで、tの進み方が呼び出し元とずれることを防ぐ。 | ||
| + | """ | ||
| + | # ノードに自身か作成された時刻を持たせ、作成時刻が最新バージョンより古ければコピー、同じなら使い回す | ||
| + | t_new = len(self.roots) - 1 | ||
| + | node = self.roots[-1] | ||
| + | m = self.m | ||
| + | |||
| + | while i > 0: | ||
| + | child = node.children[i % m] | ||
| + | if child.created < t_new: | ||
| + | child = child.copy(t_new) | ||
| + | node.children[i % m] = child | ||
| + | node = child | ||
| + | i //= m | ||
| + | |||
| + | node.value = x | ||
| + | |||
| + | def debug_print(self): | ||
| + | for t in range(len(self.roots)): | ||
| + | res = [] | ||
| + | for i in range(self.n): | ||
| + | res.append(self.get_value(i, | ||
| + | print(t, res) | ||
| + | |||
| + | |||
| + | class PersistentUnionFind(Generic[T]): | ||
| + | |||
| + | def __init__(self, | ||
| + | self.table = PersistentArray([-1] * n) | ||
| + | |||
| + | def root(self, x, t): | ||
| + | tbl = self.table | ||
| + | p = tbl.get_value(x, | ||
| + | while p >= 0: | ||
| + | x = p | ||
| + | p = tbl.get_value(x, | ||
| + | return x | ||
| + | |||
| + | def find(self, x, y, t): | ||
| + | return self.root(x, | ||
| + | |||
| + | def unite(self, x, y, t): | ||
| + | r1 = self.root(x, | ||
| + | r2 = self.root(y, | ||
| + | if r1 == r2: | ||
| + | return False | ||
| + | d1 = self.table.get_value(r1, | ||
| + | d2 = self.table.get_value(r2, | ||
| + | if d1 <= d2: | ||
| + | self.table.update(r2, | ||
| + | self.table.update_newest(r1, | ||
| + | else: | ||
| + | self.table.update(r1, | ||
| + | self.table.update_newest(r2, | ||
| + | return True | ||
| + | |||
| + | def get_size(self, | ||
| + | return -self.table.get_value(self.root(x, | ||
| + | |||
| + | </ | ||
| + | |||
| + | ++++ | ||
| + | |||
| + | |||
| + | ==== ポテンシャル付きUnion-Find ==== | ||
| + | |||
| + | 重み付きUnion-Findともいう。 | ||
| + | |||
| + | * [[https:// | ||
| + | |||
| + | 頂点間の「距離」も管理できるUnion-Find。 | ||
| + | |||
| + | 「各頂点 $i$ に何らかの値 $W_i$ が決まっているが直接は観測できなくて、頂点間の差分だけがわかる」というときに、 | ||
| + | 矛盾するかしないか、しない場合に指定した2頂点間の差分はいくつになるか、を求める。 | ||
| + | |||
| + | | ||
| + | -2↗↖5 | ||
| + | ② | ||
| + | | ||
| + | ⑤ ⑦ | ||
| + | | ||
| + | ② - ① = -2 | ||
| + | ③ - ① = 5 | ||
| + | ⑤ - ① = 4 | ||
| + | ③ - ② = 7 | ||
| + | ⑦ - ⑤ = 2 | ||
| + | ⑥ - ② = 不定（同じ連結成分では無いため） | ||
| + | |||
| + | 以下のような特徴を持ったデータ構造である。 | ||
| + | |||
| + | * '' | ||
| + | * '' | ||
| + | * '' | ||
| + | * '' | ||
| + | |||
| + | 通常のUnion-Findに加え、親を $0$ とした時の各頂点の値を記録していく。\\ | ||
| + | 根（代表）まで辿っていけば、「根を $0$ とした時の自身の値」がわかり、同一グループ内なら比較ができるようになる。 | ||
| + | |||
| + | 値の更新に気をつければ経路圧縮もできるので、各計算量は $O(\alpha(N))$ となる。 | ||
| + | |||
| + | === 実装 === | ||
| + | |||
| + | ++++ Python3 | | ||
| + | |||
| + | <sxh python> | ||
| + | from typing import Callable, Generic, TypeVar, List | ||
| + | |||
| + | T = TypeVar(' | ||
| + | |||
| + | |||
| + | class UnionFindWithPotential(Generic[T]): | ||
| + | |||
| + | def __init__(self, | ||
| + | n: int, | ||
| + | init: Callable[[], | ||
| + | func: Callable[[T, | ||
| + | | ||
| + | """ | ||
| + | :param n: | ||
| + | :param init: 単位元の生成関数 | ||
| + | :param func: 2項間加算関数（add） | ||
| + | :param rev_func: 逆関数（sub） | ||
| + | """ | ||
| + | self.table: List[int] = [-1] * n | ||
| + | self.values: | ||
| + | self.init: Callable[[], | ||
| + | self.func: Callable[[T, | ||
| + | self.rev_func: | ||
| + | |||
| + | def root(self, x: int) -> int: | ||
| + | stack = [] | ||
| + | tbl = self.table | ||
| + | vals = self.values | ||
| + | |||
| + | while tbl[x] >= 0: | ||
| + | stack.append(x) | ||
| + | x = tbl[x] | ||
| + | if stack: | ||
| + | val = self.init() | ||
| + | while stack: | ||
| + | y = stack.pop() | ||
| + | val = self.func(val, | ||
| + | vals[y] = val | ||
| + | tbl[y] = x | ||
| + | return x | ||
| + | |||
| + | def is_same(self, | ||
| + | return self.root(x) == self.root(y) | ||
| + | |||
| + | def diff(self, x: int, y: int) -> T: | ||
| + | """ | ||
| + | x と y の差（y - x）を取得。同じグループに属さない場合は None。 | ||
| + | """ | ||
| + | if not self.is_same(x, | ||
| + | return None | ||
| + | vx = self.values[x] | ||
| + | vy = self.values[y] | ||
| + | return self.rev_func(vy, | ||
| + | |||
| + | def unite(self, x: int, y: int, d: T) -> bool: | ||
| + | """ | ||
| + | x と y のグループを、y - x = d となるように統合。 | ||
| + | 既に x と y が同グループで、矛盾する場合は AssertionError。矛盾しない場合はFalse。 | ||
| + | 同グループで無く、新たな統合が発生した場合はTrue。 | ||
| + | """ | ||
| + | rx = self.root(x) | ||
| + | ry = self.root(y) | ||
| + | vx = self.values[x] | ||
| + | vy = self.values[y] | ||
| + | if rx == ry: | ||
| + | assert self.rev_func(vy, | ||
| + | return False | ||
| + | |||
| + | rd = self.rev_func(self.func(vx, | ||
| + | self.table[rx] += self.table[ry] | ||
| + | self.table[ry] = rx | ||
| + | self.values[ry] = rd | ||
| + | return True | ||
| + | |||
| + | def get_size(self, | ||
| + | return -self.table[self.root(x)] | ||
| + | |||
| + | </ | ||
| + | |||
| + | ++++ | ||
| + | |||
| + | ==== Retroactive Union-Find ==== | ||
| + | |||
| + | FIXME | ||
| + | |||
| + | |||
