UnionFind(DSU)を気合いで書いた話

Syntax_Error_

タイトル通り、UnionFindを気合いで書きました。
大体45分くらいかかったかなと思います。
書いている途中はほかの記事を読んだりすることはせず、今までに見た記憶をたどったり、まあ何とかなるやろ！の気持ちで書きました。
一応以前にいろいろな記事を見ていたことがあるので完全に1から作ったわけではないですが…
誰か添削すべき点があれば直してくださると助かります…
int型にしているのはACLでint型だったのと、その理由としてvectorの初期化にはO(N)かかり、N≤10⁸程度である必要があるので、わざわざ long long使う意味ないと感じたためです。

コード

#include <bits/stdc++.h>
using namespace std;

struct UnionFind {
  UnionFind(int n) : parent(n, -1), siz(n, 1) {}
  bool merge(int a, int b) {
    a = root(a);
    b = root(b);
    if (a == b) return false;
    if (siz[a] < siz[b]) swap(a, b);
    parent[b] = a;
    siz[a] += siz[b];
    return true;
  }
  bool same(int a, int b) { return root(a) == root(b); }
  int root(int x) {
    if (parent[x] == -1) return x;
    cout << x << endl;
    return parent[x] = root(parent[x]);
  }
  int size(int x) { return siz[root(x)]; }
 private:
  vector<int> parent;
  vector<int> siz;
};

メモ

簡単に書いた順番と(素人)解説を主に自分用のメモとして残しておきます。

書いた順番

  1. コンストラクタ

  2. root

  3. same

  4. merge

  5. size

コンストラクタ

親と集合の大きさを保持するvectorを初期化します。
今回は親の親は-1として保持するようにしました。(初期化が楽です。)最初はforで0からやろうかと思いましたが、きたなくなったのでやめました。

root

これよく覚えてたなと思います。
前述のとおり、親の時はparent[x]==-1なので自身を返すようにします。
それ以外の時では、再帰的にparent[x]を呼び出して返すようにします。
その際にparent[x]=root(parent[x])としておくことで親に根を付け替えておきます。このようにすることで常に深さが小さくなるので高速化されます(これだけでO(log N)になるらしい)

same

親が同じかを見るだけ
特にいうことなし！

merge

実は一回実装に失敗してます…AOJのUnionFindTreeでテストした際にずっとエラーにしかならず…そのテストケースを引っ張ってきてデバッグしたところ、if(a==b)の判定が抜けていたためバグっていたようでした(致命的)。
今回は union by sizeを採用しているため、siz[a]<siz[b]の時はaとbを入れ替えています。
つまり、小さいほうの木を大きいほうの根元につなげるようにしています。その方が効率的にできます。(O(log N)になるらしい)

size

親のみが正しいサイズを持っている(親以外は無視するような設計)ので、root(x)で親を取得してそれをそのまま返します。

技術的なまとめ

rootで経路圧縮してO(log N)
union by size でO(log N)
この実装で、全体としてはO(α(N))になります(なるらしい)
ここらへんはよくわかりません…

追記たち

別ファイルで一回実験してみました。
int num_rootを定義し、コンストラクタでnum_root(n)で初期化、merge毎にnum_rootをデクリメント
int numRoot()で取得できるようにした。
O(α(N+M))をO(α(M))に改善したはず…！
→なぜかちょっと遅くなった
制約が狭かったことゆえの誤差なのでしょうか…？

…！？？

そりゃ遅いわ等ご指摘があれば、教えていただけると幸いです。
提出コード
①https://atcoder.jp/contests/arc032/submissions/31937467
②https://atcoder.jp/contests/arc032/submissions/31937619

いいなと思ったら応援しよう！