素集合データ構造 (Union-Find data structure, Disjoint-set data structure)

概要

Union-Findでは以下の操作を行うことができる

  • \(union(u, v)\) : 要素uの属するグループと要素vが属するグループを１つにまとめる

  • \(find(u)\) : 要素uが属するグループを求める

\(find(u) = find(v)\) であればuとvは同じグループに属することが分かる

計算量

以下を行うことにより \(O(\alpha(n))\) になる。 (\(\alpha\) はアッカーマン関数の逆関数)

  • rankもしくはsizeによるマージ先の選択

  • 経路圧縮

片方のみだと \(O(\log n)\) になる。

実装 (Union by rank)

rankによってマージ先を選択する実装

N = 10**5

*p, = range(N)
rank = [1]*N
def root(x):
    if x == p[x]:
        return x
    p[x] = y = root(p[x])
    return y
def unite(x, y):
    px = root(x); py = root(y)
    if px == py:
        return 0
    rx = rank[px]; ry = rank[py]
    if ry < rx:
        p[py] = px
    elif rx < ry:
        p[px] = py
    else:
        p[py] = px
        rank[px] += 1
    return 1

実装 (Union by size)

size(集合のサイズ)によってマージ先を選択する実装

N = 10**5

*p, = range(N)
size = [1]*N
def root(x):
    if x == p[x]:
        return x
    p[x] = y = root(p[x])
    return y
def unite(x, y):
    px = root(x); py = root(y)
    if px == py:
        return 0
    sx = size[px]; sy = size[py]
    if sy < sx:
        p[py] = px
        size[px] += sy
    else:
        p[px] = py
        size[py] += sx
    return 1

実装 (Linking by index)

シンプルなUnion-Find実装。

インデックスの若い方を親にしてマージする実装
計算量的には "by size" と同じになることが示せる。しかし、実際の処理では少しだけ遅くなる(rootの呼ばれる回数が多くなる)。

シンプルな実装であるため、Pythonではちょっと高速になることが多い。(PyPyではby rankの方が高速)

# Union-Find data structure

N = 10**5

*p, = range(N)
def root(x):
    if x == p[x]:
        return x
    p[x] = y = root(p[x])
    return y
def unite(x, y):
    px = root(x); py = root(y)
    if px == py:
        return 0
    if px < py:
        p[py] = px
    else:
        p[px] = py
    return 1

参考

戻る