Algoogle

Algorithm for Programming Contest

Union Find Tree

基本情報


計算量
用途 データの集合の併合と同じ集合に属しているかの判定

N := 頂点数
:= アッカーマン関数の逆関数

解説


Union Find木では共通の親を持つかどうかで同じ木に属しているか判定する.
また, 2つの要素を併合する場合は片方の親の子にもう片方の木を入れる.
偏りをなくすために木のランクを保存しておいてランクの高い方に小さい方を併合するようにする.
親を見つけるときにその途中結果をメモする(親に直接つなぐ).

コード


(union_find.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
struct union_find {
    int rnk[MAX], par[MAX];

    union_find(int n) { for(int i = 0; i < n; i++) rnk[i] = 1, par[i] = i; }

    int find(int x) {
        if(x == par[x]) return x;
        else return par[x] = find(par[x]);
    }
    void unite(int x, int y) {
        x = find(x); y = find(y);
        if(x == y) return;
        if(rnk[x] > rnk[y]) par[y] = x;
        else{
            par[x] = y;
            if(rnk[x] == rnk[y]) rnk[y]++;
        }
    }
    bool same(int x, int y) {
        x = find(x); y = find(y);
        return x == y;
    }
};

問題


Comments