リリース・改善中
Algorithm
Union-Find（素集合データ構造）は要素を互いに重ならないグループに分け、グループの併合や同じグループかどうかの判定をほぼ定数時間で行います。
Union-Find は素集合データ構造（disjoint set）とも呼ばれ、要素の集まりを互いに重ならない集合に分けて管理します。操作は二つだけです。find は要素が属する集合の代表元を返し、union は二つの要素が属する集合を一つに併合します。各集合は親へのポインタでできた木として保存され、木の根がその集合の代表元になります。
つながりが増える一方で「この二つはつながっているか」を何度も問い合わせる場面では、毎回グラフを探索するより Union-Find のほうがはるかに高速です。経路圧縮とランク・サイズによる併合を組み合わせると、1 回あたりのならし計算量は逆アッカーマン関数 α(n) まで下がり、現実のどんな入力でもこの値は 4 を超えません。クラスカル法の最小全域木、閉路検出、連結成分の計算、アカウント統合のようなグループ化問題の定番の道具であり、競技プログラミングやコーディング面接にもよく登場します。
まず parent 配列一つで find と union を実装し、最適化なしでは木が一直線に伸びてしまう様子を手で追ってみてください。次にサイズによる併合と経路圧縮を一つずつ加え、木の深さがどう変わるかを確かめると仕組みがはっきりします。最後に連結成分、閉路検出、クラスカル法の問題を解き、union の戻り値を活用する習慣を身につけましょう。
find は親をたどって根（代表元）を見つけ、union は一方の根をもう一方の根の下につないで二つの集合を併合します。
find が通過したノードを根に直接つなぎ直して木を平らにするため、以降の呼び出しが速くなります。
小さい木を大きい木の下につなぐことで、どの木の高さも log n 以下に保たれます。
二つの最適化を併用すると m 回の操作が O(m α(n)) で終わり、逆アッカーマン関数 α(n) は実用上 4 以下です。
DSU クラスは parent と size の二つの配列で集合を保存します。find は親をたどりながら各ノードを祖父ノードにつなぎ直す経路半減で木を平らに保ち、union は小さい集合を大きい集合の下につなぎ、すでに同じ集合なら False を返します。例では 6 個の要素を三つのグループにまとめ、同じ集合かどうかの判定と集合の数を出力します。
union_find.py
class DSU:
def __init__(self, n):
self.parent = list(range(n))
self.size = [1] * n
def find(self, x):
while self.parent[x] != x:
self.parent[x] = self.parent[self.parent[x]] # path halving
x = self.parent[x]
return x
def union(self, a, b):
ra, rb = self.find(a), self.find(b)
if ra == rb:
return False
if self.size[ra] < self.size[rb]:
ra, rb = rb, ra
self.parent[rb] = ra
self.size[ra] += self.size[rb]
return True
dsu = DSU(6)
for a, b in [(0, 1), (1, 2), (3, 4)]:
dsu.union(a, b)
print(dsu.find(2) == dsu.find(0)) # True
print(dsu.find(4) == dsu.find(5)) # False
print(len({dsu.find(x) for x in range(6)})) # 3
python union_find.pyインストールから Union-Find の中心となる考え方まで、6 章で順を追って学びます。
Union-Find について質問し、経験を共有し、意見を交わす場所です。
まだディスカッションはありません。最初の話題を始めましょう。
コメント 0件
ログイン · ログインするとコメントできます。
最初のコメントを書いてみましょう。