4日目: Weighted UnionFindを実装する

競プロ用ライブラリを作る Advent Calendar 2024の4日目です.

Weighted UnionFindって?

「値の差」みたいな情報を速く計算出来るデータ構造です.
$N$個の数値$x_1, x_2, ..., x_N$について

• 「$x_i - x_j = X$だ」というような情報を追加する

• $x_i - x_j$ の値を調べ

  • 情報が不足している
  • 情報が矛盾している
  • 答えは$X$だ

  のどれかの返答をする

という操作が$O(\alpha(n))$みたいな計算量でできます. ($\alpha$は前日にも出てきたアッカーマン関数の逆関数です)

このデータ構造ができることを考えると「重み付きUnionFind」ではなく「ポテンシャル付きUnionFind」が正しいという話があったりします.
ですが, 私の場合PotentialよりもWeightedの方が速くタイピングできて競プロに有利なので, ここではWeighted UnionFindという呼び方をすることにします.

仕組み

UnionFindに追加の情報を乗せます.
UnionFindで木の親を指す情報を持っていましたが, そこに親との値の差も持つようにします.
そして根の要素はグループのサイズに加えて「そのグループ内で矛盾した情報が無いか」という情報も管理します.

抽象化

抽象化すると群が乗ります.
更に抽象化するとGroupoid (全ての射が同型射な圏) にもできますが, Rustの表現能力だと実装にほとんど差が無いので気にしないで良いです.

一般の群は交換法則が成り立たないので順番には気をつけて実装しましょう.

実装

• weightedunionfind.rs

パフォーマンスを良くするために非再帰でfindを書きたいですが, 昨日のUnionFindと同じ方法だと辛いので経路圧縮の方法を変えます.
Path Halvingという名前で,

こういうのを

こういう風に1つ飛ばしで繋ぎなおす経路圧縮です. これでも$O(\alpha(N))$が保証されるらしいです.

まとめ

いかがでしたか?

明日は前日のUnionFindを使った最小全域木のアルゴリズムを実装します.