Union-Find木とは
Union-FindまたはDisjoint Setとは、蟻本の言葉を借りると「グループ管理のためのデータ構造」。
・要素aと要素bが同じグループかどうか
・aが属するグループと、bが属するグループを併合(unite)する
ということをしたいときに使います。
Union-Find木(深さバージョン)の実装
蟻本に書いてあるとおりの実装。
グループの併合のとき、木の深さが深いものに浅いものを併合する。
あまり使わない。競プロでは後述のサイズバージョンばかり使用している。
class UnionFindVerDepth():
def __init__(self, N):
""" N個のノードのUnion-Find木を作成する """
self._parent = [n for n in range(0, N)]
self._depth = [1] * N
def find_root(self, x):
""" xの木の根(xがどのグループか)を求める """
if self._parent[x] == x: return x
self._parent[x] = self.find_root(self._parent[x])
return self._parent[x]
def unite(self, x, y):
""" xとyの属するグループを併合する """
gx = self.find_root(x)
gy = self.find_root(y)
if gx == gy: return
if self._depth[gx] < self._depth[gy]:
self._parent[gx] = gy
else:
self._parent[gy] = gx
if self._depth[gx] == self._depth[gy]: self._depth[gx] += 1
def get_depth(self, x):
""" xが属するグループの深さを返す """
return self._depth[self.find_root(x)]
def is_same_group(self, x, y):
""" xとyが同じ集合に属するか否か """
return self.find_root(x) == self.find_root(y)
def calc_group_num(self):
""" グループ数を計算して返す """
N = len(self._parent)
ans = 0
for i in range(N):
if self.find_root(i) == i:
ans += 1
return ans
Union-Find木(サイズバージョン)の実装
Union-Findのサイズバージョン。
グループの併合のとき、グループのサイズ(ノードの個数)が大きいものに、小さいものを併合させる。
競プロでは大抵、ノードの個数やグループ数の最小値とかを求めるので、こちらを使うことが多い。
class UnionFindVerSize():
def __init__(self, N):
""" N個のノードのUnion-Find木を作成する """
self._parent = [n for n in range(0, N)]
self._size = [1] * N
def find_root(self, x):
""" xの木の根(xがどのグループか)を求める """
if self._parent[x] == x: return x
self._parent[x] = self.find_root(self._parent[x])
return self._parent[x]
def unite(self, x, y):
""" xとyの属するグループを併合する """
gx = self.find_root(x)
gy = self.find_root(y)
if gx == gy: return
if self._size[gx] < self._size[gy]:
self._parent[gx] = gy
self._size[gy] += self._size[gx]
else:
self._parent[gy] = gx
self._size[gx] += self._size[gy]
def get_size(self, x):
""" xが属するグループのサイズ(個数)を返す """
return self._size[self.find_root(x)]
def is_same_group(self, x, y):
""" xとyが同じ集合に属するか否か """
return self.find_root(x) == self.find_root(y)
def calc_group_num(self):
""" グループ数を計算して返す """
N = len(self._parent)
ans = 0
for i in range(N):
if self.find_root(i) == i:
ans += 1
return ans
使い方
N = 10
uf = UnionFindVerSize(N)
uf.unite(0, 1)
uf.unite(1, 2)
uf.unite(2, 3)
uf.unite(4, 5)
uf.unite(4, 6)
a = uf.find_root(2)
print(a)
a = uf.get_size(2)
print(a)
a = uf.is_same_group(3, 4)
print(a)
a = uf.calc_group_num()
print(a)
Union-Find木を使う問題
(あともう一問くらいあった気がするけど忘れた)