Union Findとは
Union Findとは、
です。
主に以下の2つの操作を高速に処理することができます。
ただし、グループの統合はできても分割はできません。
基本的な構造
ユニオンファインドは、木（ツリー構造） を使ってグループを管理します。
初期状態
最初はすべての要素が自分自身が親になっています。
UNION操作（統合）
2つの要素を同じグループにする操作です。
要素1と2を同じグループに統合するには、片方の親をもう一方の親にします。
FIND操作（統合）
ある要素の親を取得する操作です。
要素2の親は木を辿っていくと親である要素1を見つけることができます。
効率を向上させるテクニック
UnionFindを高速化させるため、以下の2つの手法がよく使われます。
経路圧縮
経路途中の要素の親を直接ルートにつなげることで木が浅くなり、検索を高速化することができます。
ランクによる併合
木の高さが低い方を高いほうに繋ぐことで、木の高さを抑えることができます。
実装(Python)
実装
class UnionFind:
def __init__(self, n):
self.parent = [-1] * n
self.rank = [0] * n
def is_root(self, node):
return self.parent[node] == -1
def find(self, node):
if self.is_root(node):
return node
self.parent[node] = self.find(self.parent[node]) # 経路圧縮
return self.parent[node]
def union(self, node1, node2):
root1 = self.find(node1)
root2 = self.find(node2)
if root1 == root2:
return
if self.rank[root1] < self.rank[root2]:
smaller, bigger = root1, root2
else:
smaller, bigger = root2, root1
self.parent[smaller] = bigger
self.rank[bigger] = max(self.rank[bigger], self.rank[smaller] + 1)
参考文献
コメント