Union-Findって何？？
Union-Find（またはDisjoint-Setとも呼ばれる）とは、データ構造とアルゴリズムの一種で、主に集合の操作を効率的に行うために使用され、主に連結成分の追跡や分離に役立つ。
Union-Findの概要
Union-Findデータ構造は、主に以下の2つの操作ができる。
- Union（結合）
- 2つの集合を1つに結合する。つまり、2つの要素が同じ集合に属するようになる。
- Find（検索）
- 与えられた要素がどの集合に属しているかを検索する。連結成分の特定ができる。
Union-Findのメリット
- 高速な操作
- 平均的に非常に高速な計算ができる。
- 連結成分の管理
- 連結成分を効率的に管理するのに適しているので、グラフ内の連結成分を追跡する際に役立つ。
- 簡潔な実装
- 実装が比較的簡単で、少ないコードでUnionとFind操作ができる。
Union-Findのデメリット
- 要素の追加と削除
- Union-Findは主に要素の連結成分を管理するため、要素の追加と削除には向いていない。要素の追加や削除が頻繁に行われる場合、他のデータ構造が適している可能性が高い。
ここから下は正直よくわからなかったので知っている方いればコメントお願いします🙏
- 平衡性の維持
- 不適切なUnion操作の順序や結合の方法によって、データ構造が非平衡化され、操作の時間複雑度が劣化することがあります。この問題に対処するために、平衡木を使用することがあります。
- 特定のアプリケーションに制限される
- Union-Findは主に連結成分の追跡に使用されますが、他のデータ構造やアルゴリズムには適さない場合があります。そのため、使用ケースに制限があります。
例題1
問題の概要
N 頂点の、単純とは限らない無向グラフを考えます。 初期状態では、頂点のみが存在し、辺は全く存在せず、以下の 2 種類のクエリが、Q 回与えられます。
連結クエリ： 頂点 A と、頂点 B を繋ぐ辺を追加します。
判定クエリ： 頂点 A と、頂点 B が、連結であるかどうか判定します。
連結であれば Yes、そうでなければ No を出力します。
連結であるとは、頂点 A から頂点 B まで辺をたどって到達可能であることを意味します。
連結クエリによって頂点 A,B 間の辺が追加されると、A から B へも B から A へも辿れるようになります。
入力
$N\quad Q$
$P_1\quad A_1\quad B_1$
$P_2\quad A_2\quad B_2$
$:$
$P_Q\quad A_Q\quad B_Q$
回答
おそらく一番シンプルな書き方です
class UnionFind:
def __init__(self, n):
self.parents = list(range(n))
def find(self, x):
if self.parents[x] == x:
return x
else:
self.parents[x] = self.find(self.parents[x])
return self.parents[x]
def union(self, x, y):
root_x, root_y = self.find(x), self.find(y)
if root_x == root_y: return
self.parents[root_x] = root_y
def same(self, x, y):
return self.find(x) == self.find(y)
n, q = map(int, input().split())
uf = UnionFind(n)
for _ in range(q):
p, a, b = map(int, input().split())
if p:
print('Yes' if uf.same(a, b) else 'No')
else:
uf.union(a, b)
classの説明は省きます
僕が一番躓いたとこはparentsに入っている値です
初期値(n=5の時)
self.parents = list(range(n))
このようになってます。
一つ目のクエリが与えられるとします
0 1 2
P=0なので連結クエリです。つまり、1の頂点と2の頂点が辺で結ばれます。
このようにグループを結合するときはunion関数を使います
このようにparents[1] = 2となります
二つ目のクエリ
0 2 3
同じようにunion関数を使う
ここで、今の頂点について考えてみましょう
クエリ1で、頂点1と頂点2が辺で結ばれ、
クエリ2で、頂点2と頂点3が辺で結ばれたので以下の図のようになっています
しかし、parentsは、
[0, 2, 3, 3, 4]
となっています。
同じグループならparentsが同じになるとは限らないことを押さえておきましょう
ここから同じグループかどうかをfind関数で判定していきます
頂点1と頂点3が同じグループかを調べる
uf.find(1) == uf.find(3)
これで調べられます
まず、uf.find(1)をすると、parents[1]の要素を確認します。
このとき1番目には2が入っているので、次にparents[2]を見ます
2番目には3が入っているので、さらにparents[3]を見ます
3番目には3が入っています。
ここでparentsのインデックス番号と中身の要素の番号が一致しているので、一番根本の親を見つけることができました！
よって、uf.find(1)は3をreturnします。
これで調べたい2つの頂点の親をそれぞれ調べ、一致していたら辺で繋がれているということがわかります！
（実際のコードでは再帰させて親をたどっています）
ここまでで先ほど書いたコードを見てもらえるとある程度理解できるかなと思います！ここまでわかると応用も簡単にできると思うので、ぜひ入力値が2値の関係性を示す場合は検討してみてください