ポテンシャル付きUnionFindです． 実装はこちら ．

使用法

UnionFind uf(N);       // 普通のUnionFind (ポテンシャル無し)
ld = uf.merge(a, b);   // マージ．新しいリーダを返す
ld = uf.leader(a);     // リーダ
ng = uf.num_groups();  // 全体のグループ数 ( == リーダの数)
sz = uf.group_size(a); // a が属するグループのサイズ

グループの要素のリストを得るためには，前処理として，GroupInfo を作る必要がある． これには，$O(N)$ かかる．

auto gi = uf.group_info();
for (int i : gi.group(a)) cout << i << endl;  // a が属するグループの要素の列挙

ポテンシャル付きにするためには，テンプレートパラメタで，ポテンシャルの型を渡す． (デフォルトの型は，UFDummyAlg なるものになっている)

UnionFind<ll> uf1(N);
UnionFind<ftwo> uf2(N);

必要があれば，零元，和，単項マイナスを渡すこともできる:

UnionFind<ll> uf3(N, 0LL, plus<ll>(), negate<ll>());

ポテンシャル付きの時には，merge のときの第3引数に，ポテンシャルを渡さなければならない (省略不可)． merge の返却値は，ポテンシャルが無いときと同じで，リーダである．

ld = uf.merge(a, b, p);   // b を基準にした a のポテンシャルが p である．p の型は T

ポテンシャルの値は，pot メソッドで取る．これの返り値型は，optional<T> である． そのグループ内で矛盾があってポテンシャルが定義できない時には，nullopt を返す． (他のグループで矛盾していても，そのグループで矛盾が無ければ nullopt にはならない．)

int ld = uf.merge(a, b, p0);
auto p = uf.pot(a);
if (p) {
  cout << "The potential of " << a << " relative to " << ld << " is " << *p << endl;
  assert(*uf.pot(a) - *uf.pot(b) == p0);
} else {
  // ここに来るのは，merge の前から矛盾していたときや，
  // a と b が同じグループに属していて，*uf.pot(a) - *uf.pot(b) が p0 と等しくなかったとき
  cout << "Potential is undefined because of inconsistency." << endl;
}

ポテンシャルは一意に決まるとは限らない． merge の時にリーダとなるほうのグループのポテンシャルの値は (矛盾しなければ) そのまま保たれる． 他方のグループのポテンシャルの値が，調整される．

ソース

キーワード: potential