Union-Find
#Data_Structure #Graph
Abstract
Union-Find (Union-Find) は, 互いに素な集合に対し,
Union: 与えられた要素$ u, vに対し, $ uが含まれる集合と$ vが含まれる集合が異なる場合に二つの集合を合併する.
Find: 与えられた要素$ vが含まれる集合の代表元を返す
の操作が行えるデータ構造.
Explanation
TODO 書く.
Implementation
再帰を利用して実装している. そういや非再帰のUnion-Findを見た覚えがない
経路圧縮, rankによる合併を行うことで, 計算量を改善している.
TODO 書く.rankを利用したUnion操作は, 俗に「マージテク」と呼ばれているらしい.
Input
Output
Time complexity
amortized$ O(\alpha (N))time. ($ \alpha(n)はAckermann関数$ A(n, n)の逆関数.)
code:python
class UnionFind:
def __init__(self, N):
# negative value: represents the root of a tree; its absolute value is the size of the tree
# positive value: the parent's index
self.vertices = -1 for _ in range(N)
self.rank = 0 * N
def find(self, v):
if self.verticesv < 0: # v is a root
return v
else:
# path compression: reconnect v to the root
self.verticesv = self.find(self.verticesv)
return self.verticesv
def union(self, u, v):
s1 = self.find(u) # the root of the tree including vertex u
s2 = self.find(v) # the root of the tree including vertex v
if s1 == s2: # u and v is in the same tree
return False
if self.ranks1 > self.ranks2: # the tree including u is taller
self.verticess1 += self.verticess2 # update the size of the bigger tree
self.verticess2 = s1
else: # the tree including v is taller
self.verticess2 += self.verticess1 # update the size of the bigger tree
self.verticess1 = s2
if self.ranks1 == self.ranks2: self.ranks2 += 1
return True
def is_connected(self, u, v):
return self.find(u) == self.find(v)
def size(self, v):
return -self.verticesself.find(v)
Verification
互いに素な集合
Unionfind
References
Union-Find木
Python:Union-Find木について
Union find(素集合データ構造)
競プロ覚書：Union-Find まとめ
Union-Find Tree を理解する！素集合系を扱うデータ構造
R. E. Tarjan, 『新訳 データ構造とネットワークアルゴリズム』, 毎日コミュニケーションズ, 2008.
T. Cormen, C. Leiserson, R. Rivest, C. Stein, 『アルゴリズムイントロダクション 第3版』, 近代科学社, 2009.