Python で素集合データ構造を実装します。
素集合データ構造
wikipedia を見てみます。
素集合データ構造（そしゅうごうデータこうぞう、英: disjoint-set data structure）は、データの集合を素集合（互いにオーバーラップしない集合）に分割して保持するデータ構造。
出典: フリー百科事典『ウィキペディア（Wikipedia）』
どういう時に使うと便利なのか良くわかりません。
素集合データ構造は、「同値関係が与えられた時に、データを同値類に分類すること」 を効率的に行うアルゴリズムです。
以下の説明が大変分かりやすかったです。
「同値関係が与えられた時に、データを同値類に分類すること」という意味で使うことが多いので注意が必要です。
Union-Find木のサンプルコード
たとえば、A, B, C, D, Eの5人がいて、そこに「AさんとBさんは友達」「DさんとEさんは友達」「BさんとCさんは友達」という情報が与えられたとします。ここで「友達の友達は友達である」という条件を与えると、「A, B, C」「D, E」という二つの友達グループにわけることができます。
このように「A, B, C, D, E」という要素の集合と、「A=B, D=E, B=C」といった同値関係の集合を与えられた時に「任意の要素が同じ同値類に属しているか」という情報が欲しくなります。これを実装するのがUnion-Find木です。
atcorder に、このアルゴリズムのとても分かりやすい解説があります。
また、以下の動画を参照して、全てを -1 で初期化し、集合のサイズをルートの負数を使って表すことで実装します。
class DisjoinSet(object):
def __init__(self, n):
# ルートは -1。最初は全てルートで、-1に初期化。
self.S = [-1 for x in range(n)]
def find(self, x):
# 負の時はルート。
if (self.S[x] < 0):
return x
# 負でないときは再帰的にルートまで回す。
self.S[x] = self.find(self.S[x])
return self.S[x]
def union(self, x, y):
# それぞれのルートを探す。
x = self.find(x)
y = self.find(y)
# サイズの大きい方（ルートは負で、小さいほうがサイズが大きい）
# がルートになる。
if self.S[x] <= self.S[y]:
self.S[x] += self.S[y]
self.S[y] = x
else:
self.S[y] += self.S[x]
self.S[x] = y
def same_check(self, x, y):
return self.find(x) == self.find(y)
def print_set(self):
print (self.S)
if __name__ == '__main__':
disjoint_set = DisjoinSet(9)
disjoint_set.union(1, 2)
disjoint_set.union(3, 4)
disjoint_set.union(5, 6)
disjoint_set.print_set()
# [-1, -2, 1, -2, 3, -2, 5, -1, -1]
disjoint_set.union(2, 3)
disjoint_set.print_set()
# [-1, -4, 1, 1, 3, -2, 5, -1, -1]
print(disjoint_set.find(4))
# 1
disjoint_set.print_set()
# [-1, -4, 1, 1, 1, -2, 5, -1, -1]
想定通りの結果を得ることができました。