【競プロメモ】Union-find Tree (暫定)

Point

各グループを木で表現する
互いに素な集合系を扱う
分割などには向いていない

うれしいこと

集合に新たな要素を加えたり集合同士をまとめるのが楽

最初に用意しておくもの

　親を記述する配列（ i の親は par[i]）が必要になる。最初の初期化で全ての要素が違うグループにいる状態をつくる。このコードでは par[i] = -1 のとき、i が根になるとする。

vector<int> par;
par.resize(N, -1);

木をつくる手順：

初期化（全ての要素が違うグループにいる状態をつくる）
外部の情報に応じて要素や木を結合していく

どんな動作がある？

根を調べる

par[i] で親を辿り続けた先に根がある。下のコードだとマイナスの値が出た時は根であるという判定になっているが色々な流派があるっぽい。自分の値（par[i] = i）にしておくなどなど。

int Root(int x) {
    if (par[x] < 0) return x;
    else return root(par[x]);
}

要素同士が同じグループに属しているかを調べる

Root で根を調べ、それぞれの根が同じなら同じグループに属している。

bool Cmp(int x, int y) {
    return Root(x) == Root(y);
}

要素や木を結合する

bool Merge(int x, int y) {
    x = Root(x); y = Root(y);
    if (x == y) return false;
    par[y] = x;
    return true;
}

計算時間短縮のために行われる工夫

上記の関数を使って、Union-find Tree を作れるが、これだと計算時間があまり早くないです。改善点は ”木が長くなってしまうことで根を辿る際に時間がかかってしまう" ところにあります。具体的に行われていることは以下の二つです。

経路圧縮をする
木をつなげるとき、短い木の根の親を、長い木の根に設定する

経路圧縮をする

木が縦に長くなってしまうのは、親を辿っている間に、辿った要素を根につなぎ変えることで O(1) で根を算出することができるようになります。

int Root(int x) {
    if (par[x] < 0) return x;
    //else return Root(par[x]);
    else return par[x] = Root(par[x]);
}

木の結合のさせ方を工夫する

長い木を短い木に結合させてしまうと、結合させた木はさらに長くなってしまいます。そのため、木をつなげるときに短い木の根の親を長い木の根に設定します。

bool Merge(int x, int y) {
    x = Root(x); y = Root(y);
    if (x == y) return false;
    if (rank[x] > rank[y]) {
        par[y] = x;
    } else {
        par[x] = y;
        if (rank[x] == rank[y]) {
            rank[y]++;
        }
    }
   return true;
}

また、要素の数で決める場合もあります。初期化の際に根の値を -1 にしておくと、グループに属する要素の数を保持しておくことができます。

bool Merge(int x, int y) {
    x = Root(x); y = Root(y);
    if (x == y) return false;
    if (par[x] > par[y]) swap(x, y);
    par[x] += par[y];
    par[y] = x;
    return true;
}

int size(int x) {
    return -par[Root(x)];
}

参考ページ（ほぼ丸パクリさせていただいたサイト。本当にお世話になっております。）

AtCoder ABC 157 D - Friend Suggestions (400 点) - けんちょんの競プロ精進記録
 Union find(素集合データ構造)
Union-Find Tree を理解する！素集合系を扱うデータ構造 | アルゴリズムロジック

De.HP

おバイクお出かけお写真とお釣りとおプログラミングとお雑記です。