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

コメント