JuliaでUnionFindを使ってみる(DisjointSets - DataStructures.jl)

お久しぶりです。まぁじです。

まえおき
実行環境
自力実装したUnionFind法
- 自力実装の利点・欠点
IntDisjointSetsを使ったUnionFind法
自力実装よりIntDisjointSetsの方が早い事例（2023/7/12追記）
参考資料

まえおき

今回はDataStructures.jlにあるDisjointSetsについてです。競技プログラマーならUnion-Find法の方が聞き覚えがあると思います。

日本語でいうと「素集合データ構造」で、木構造を用いて

グループの併合 (union / unite)
それぞれのデータが同じグループに存在するかの判定 (find)

が高速にできます。

詳しいアルゴリズムや応用はこのスライドやこのページを読むとわかりやすいと思います。

実行環境

Juliaのインストールは既に済んでいるものとします。
ちなみに使ってるエディタはVSCodeで、Julia Extensionを入れて使ってます。

julia> versioninfo()
Julia Version 1.5.3
Commit 788b2c77c1 (2020-11-09 13:37 UTC)
Platform Info:
  OS: Windows (x86_64-w64-mingw32)
  CPU: Intel(R) Core(TM) i3-8130U CPU @ 2.20GHz
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-9.0.1 (ORCJIT, skylake)

自力実装したUnionFind法

あまり複雑なアルゴリズムではないので、20行ほどで書けます。

名前	説明
par	各要素の親を表す(初期値は自分が親)。
siz	各要素を親とするグループの大きさを表す(初期値は1)。
root(x)	xの親を探す。
unite!(x,y)	xのノードとyのノードを結合。小さい方が親となる。
issame(x,y)	xのノードとyのノードの親が同じかを返す。

※ちなみに、慣例上Juliaにおいて破壊的処理は!を付けることになっているので、結合処理はunite!になってます。

あとはこれをmain関数内にペタリして処理をするだけです。

par=Vector{Int}([i for i=1:n])
siz=ones(Int,n)
function root(x::Int)
    index=par[x]
    while par[index]!=index
        index=par[index]
    end
    return index
end
function unite!(x::Int,y::Int)
    rx,ry=root(x),root(y)
    if rx==ry
        return 0
    elseif rx>ry
        rx,ry=ry,rx
    end
    par[ry]=rx
    siz[rx]+=siz[ry]
end
function issame(x::Int,y::Int)
    isequal(root(x),root(y))
end

例：ACL Beginner Contest 「C - Connect Cities」
(Submission #20614886 - ACL Beginner Contest)

自力実装の利点・欠点

DataStructures.jlを使うよりもパッケージの読み込み時間がないので早い
このコード内ですべて完結しているのでバグの原因を見つけやすい
コードが比較的長くなる
サイズMのUnion-Find木を作らなければならないところを、コピペミスしてサイズNでWA ~~(実体験)~~

IntDisjointSetsを使ったUnionFind法

DataStructures.jlのインストール

DataStructures.jlがインストールされていない場合、先にPkgを開いてインストールしてください。

コマンド入力時に]を押すとPkgのコマンドを入力できます。

(@v1.5) Pkg> add "DataStructures"

(Int)DisjointSetsの説明

DataStructures.jl内にはDisjointSetsとIntDisjointSetsが存在します。
DisjointSetsはIntDisjointSetsのラッパーであり、辞書を用いてマッピングしているのでChar型とか数字以外でもUnionFindができるらしいです(必要か？)。
※d=DisjointSets(1:N)と宣言することで同様に使えます。

名前	説明
IntDisjointSets(N)	要素数NのUnionFind木を宣言。
union!(d,x,y)	xのノードとyのノードを結合。xが親になる。
root_union!(d,x,y)	xのノードとyのノードのそれぞれ親を結合。
find_root!(d,x)	xのノードの親を返す。
in_same_set(d,x,y)	xのノードとyのノードが同じグループにあるかを返す。
d.ngroups	木構造内のグループ数を返す。
num_groups(d)	おそらくd.ngroupsと同様。

# プログラムの例
using DataStructures
uf=IntDisjointSets(5)
union!(uf,2,3)
@show uf 

root_union!(uf,1,3)  #ここをunion!(uf,1,3)にすると1の親が2になる
@show uf

@show find_root!(uf,3)
@show in_same_set(uf,1,4)
@show uf.ngroups
@show num_groups(uf)

# 出力。@showに各行が対応
uf = IntDisjointSets{Int64}([1, 2, 2, 4, 5], [0, 1, 0, 0, 0], 4)
uf = IntDisjointSets{Int64}([1, 2, 1, 4, 5], [1, 1, 0, 0, 0], 3)
find_root!(uf, 3) = 1
in_same_set(uf, 1, 4) = false
uf.ngroups = 3
num_groups(uf) = 3