Union-Findとは
Union-Findは、グループ分けを管理できるデータ構造です。主に2つの操作を行うことができます。
- グループの接合（Union）
- グループに属するかの判定（Find）
これら2つが行えるため、Union-Findと呼ばれます。
Union-Findの実装
PythonでUnion-Findを実装する方法を見てみましょう。
まず、各要素の親をpar（parentsの略）で管理します。最初は各要素はどこのグループにも属していないので、自分自身が親になります。
N = 10 # 要素数
par = [i for i in range(N+1)]
次に、自分の親を見つける関数find、要素x,yが同じグループかを確認する関数sameを定義します。
def find(x):
if par[x] == x:
return x
else:
par[x] = find(par[x]) # 経路圧縮
return par[x]
def same(x, y):
return find(x) == find(y)
最後に、それぞれの親を確認して異なる場合のみ親を統一する関数uniteを定義します。
def unite(x, y):
x = find(x)
y = find(y)
if x == y:
return
par[x] = y
以上がPythonによる最低限の実装でした。