Union-Findで連結を管理

グループを併合し、同じグループかを高速に調べます。辺を追加していく問題と相性がよい構造です。

言語：Python / 計算量：償却 O(α(N)) / 操作

考え方

各グループの代表を根とします。
小さい木を大きい木へつなぎます。
根を探す途中の経路を短縮します。

具体例

0と1を併合、1と2を併合すると、0と2も同じグループです。辺そのものは保存しません。

実装

p = [-1]*4
def root(x):
    while p[x] >= 0:
        if p[p[x]] >= 0: p[x] = p[p[x]]
        x = p[x]
    return x
def merge(a,b):
    a,b=root(a),root(b)
    if a==b: return False
    if p[a]>p[b]: a,b=b,a
    p[a]+=p[b];p[b]=a
    return True
merge(0,1);merge(1,2)
print(root(0)==root(2))

注意する条件

通常のDSUは辺の削除や最短距離には対応しません。

確認問題

5頂点で0-1、1-2だけを併合。成分数は？

解答と理由

{0,1,2}、{3}、{4} の3成分です。

実装課題

この実装の p を6頂点で初期化し、(0,1),(2,3),(1,2) を併合。頂点0の成分サイズを出してください。入力なし。

出力:
4

参考実装

p = [-1]*6
def root(x):
    while p[x]>=0:
        x=p[x]
    return x
def merge(a,b):
    a,b=root(a),root(b)
    if a==b:return
    if p[a]>p[b]:a,b=b,a
    p[a]+=p[b];p[b]=a
for a,b in [(0,1),(2,3),(1,2)]:merge(a,b)
print(-p[root(0)])

読了の記録・下書き・メモへ