互いに素な集合(Disjoint-set・Union-find)

データ構造

2つの集合が共通する要素を持たない時に「互いに素」であると言い、このような集合の集まりを「素集合系」などと言います。

素集合系
素集合系の例

素集合系は、いくつかの木構造を用いることで管理することができます。1つの集合は1つの木を用いて表現され、各ノードが集合に含まれる元になります。

このような木を Union-find Tree と言います。

Union-find Tree
素集合系の例の時のUnion-find Tree

工夫をすれば、集合に新たな要素を加えるor集合同士をまとめる操作や、同じ集合に要素があるかを判定する操作を\(O(logn)\)よりも高速に行うことができます。

Union-find Tree

Union-find Tree はデータを互いに素な集合(素集合系)にして管理するためのデータ構造です。主に以下の操作が行えます。

  • makeTree(x) : 新しく x を根とした木をつくる
  • findRoot(x) : xを含む木の根(root)を求める。木の根を代表点(representative)と言ったりする。
  • union(x,y) : 指定された2つ要素 x,y を含む木を併合する
  • isSame(x,y) : x,y が同じ木(集合)にあるのかを、根が同じかで判定する

1つの木が、1つの集合を表しています。工夫をすれば、木(集合)同士の併合や、同じ集合に含まれているかの判定は高速にできます。

しかし、一度まとめた集合を分割したり、ノードを削除したりするのにはあまり向いていません。

まずは、なにも工夫しない場合における操作を詳しく見ておきましょう。

makeTree(a)

makeTree(x) によって、新しく a を根とした木をつくることができます。例えば、makeTree(2)では以下のようになります。

makeTree(2)によってできる木
void makeSet(int x) {
    parents[x] = x; // parents[i]:=iの親
}

findRoot(x)

findRoot(x)によって、xを含む木の根、つまり代表となる点を求めます。例えば、以下のような木に対してfindRoot(6)を行った場合は、代表点である4を返します

int findRoot(int x) {
    if (x == parent[x])
        return x;
    return findRoot(parent[x]);
}

union(x,y)

2つの木をつなげることを考えましょう。以下の図の時を例に考えます。

union(3,5) によって、3を含む木と5を含む木を1つにまとめます。出来上がる木の代表点は、もともとの木の2つの代表点のどちらかになるようにしましょう。

void unite(int x, int y) {
    x = findRoot(x);
    y = findRoot(y);
    if (x != y)
        parents[x] = y;
}

高速化の工夫

先程の実装のように、普通に木を作って何も考えずに併合することを繰り返すと、以下のように木が長くなってしまう可能性があります。

木の高さが頂点数と同じ例
木の高さが頂点数と同じ例

こうなると、例えば findRoot(9) などを行うとき、木の下から順番に全てのノードをたどる必要があるので、頂点数 n に応じた時間がかかってしまい効率が悪くなります。

これを防ぐためには、主に2種類の手法を組み合わせて使います。

  • 経路圧縮findRoot(x)の際にたどった頂点は、全て木の根に直接繋がるようにする
  • 高さ/サイズ による合併union(x,y) の際には、木の高さの低い物(木のサイズが小さい物)を、高い方の木の根(root)に直接つける

どちらか片方だけでも、findRoot(x)isSame(x,y) の計算量が\(O(logn)\)まで高速化できます。

経路圧縮

左図のような木について、findRoot(9)をすることを考えます。下から代表点である2へとたどるついでに、途中の点を全て2へと繋いでしまえば、右図のように木の高さが低くなります。

もとの木
経路圧縮後の木

先程の findRoot(x)を変更して、自身の親を、木の根に更新するコードにしましょう。

int findRoot(int x) {
    if (x != parents[x]) {
        parents[x] = findRoot(parents[x]); 
    }
    return parents[x];
}

この工夫により、計算量が\(O(n)\)から\(O(logn)\)になります。

高さ/サイズ による合併

以下の例において、union(2,5) によって、2を含む木と5を含む木を1つにまとめることを考えましょう。

この時、代表点2の木と代表点5の木のどちらをどちらに繋げるのかで効率が変わってきます。戦略としては主に2種類あって、

  • 木の高さが低い方を高い方へ繋げる
  • 木のサイズ(ノード数)が小さい方を大きい方へ繋げる

どちらの戦略であっても、今回は以下のようになります。

効率的な併合

逆のつなげ方をすると、以下のように木の高さが3になってしまい、計算が非効率になってしまいます。

非効率な併合

木の高さによる更新は以下のようにします。

void makeTree(int x) {
    parents[x] = x; // the parent of x is x
    rank[x] = 0;
}
void unite(int x, int y) {
    x = findRoot(x);
    y = findRoot(y);
    if (rank[x] > rank[y]) { // rankは木の高さを表す
        parents[y] = x;
    } else {
        parents[x] = y;
        if (rank[x] == rank[y]) {
            rank[y]++;
        }
    }
}

木のサイズによる更新は以下のようにします。

void makeTree(int x) {
    parents[x] = x; // the parent of x is x
    size[x] = 1;
}
void unite(int x, int y) {
    x = findRoot(x);
    y = findRoot(y);
    if (size[x] > size[y]) {
        parents[y] = x;
        size[x] += size[y];
    } else {
        parents[x] = y;
        size[y] += size[x];
    }
}

証明は難しいのでこの記事では詳しく説明しませんが、この工夫により計算量が\(O(n)\)から\(O(logn)\)になります。経路圧縮と合わせると、アッカーマン関数の逆関数\(\alpha\) を用いて、\(O(\alpha(n))\)で計算できることが知られています(\(O(logn)\)よりも高速)。

ソースコード

チェックはこちら:AOJ Disjoint Set: Union Find Tree

union by rank

まずはrankによる併合から。

#include <bits/stdc++.h>
using namespace std;
/* UnionFind:素集合系管理の構造体(union by rank)
    isSame(x, y): x と y が同じ集合にいるか。 計算量はならし O(α(n))
    unite(x, y): x と y を同じ集合にする。計算量はならし O(α(n))
*/
struct UnionFind { // The range of node number is from 0 to n-1
    //'rank[x]' is a rank of the union find tree the root of which is x.
    //'parents[x]' is the parent of x
    vector<int> rank, parents;
    // constructor
    UnionFind() {}
    UnionFind(int n) { // make n trees.
        rank.resize(n, 0);
        parents.resize(n, 0);
        for (int i = 0; i < n; i++) {
            makeTree(i);
        }
    }
    // make a union find tree
    void makeTree(int x) {
        parents[x] = x; // the parent of x is x
        rank[x] = 0;
    }
    // check whether the root of x is the same as that of y
    bool isSame(int x, int y) { return findRoot(x) == findRoot(y); }
    // unite two tree
    void unite(int x, int y) {
        x = findRoot(x);
        y = findRoot(y);
        if (rank[x] > rank[y]) {
            parents[y] = x;
        } else {
            parents[x] = y;
            if (rank[x] == rank[y]) {
                rank[y]++;
            }
        }
    }
    // travel the parents of tree recursivily to find root
    int findRoot(int x) {
        if (x != parents[x]) {
            parents[x] = findRoot(parents[x]); // change the x's parent to the root of tree.
        }
        return parents[x];
    }
};
int main() {
    int N;            // the number of nodes
    int Q;            // the number of query
    vector<int> P;    // p is a "same" or "unite" command.
    vector<int> A, B; // a and b are nodes.
    cin >> N >> Q;
    UnionFind uft(N); // make trees
    for (int i = 0; i < Q; i++) {
        int p, a, b;
        cin >> p >> a >> b;
        P.push_back(p);
        A.push_back(a);
        B.push_back(b);
    }
    for (int i = 0; i < Q; i++) {
        if (P[i] == 0)
            uft.unite(A[i], B[i]);
        else if (P[i] == 1) {
            if (uft.isSame(A[i], B[i]))
                cout << "1\n";
            else
                cout << "0\n";
        }
    }
    return 0;
}

union by size

サイズによる併合のバージョンです。集合のサイズが分かるという利点があります。

/*  union_find_tree_size.cpp
    素集合系を union-find tree で管理するライブラリ
    併合時の工夫:union by size
*/
#include <bits/stdc++.h>
using namespace std;
/* UnionFind:素集合系管理の構造体(union by size)
    isSame(x, y): x と y が同じ集合にいるか。 計算量はならし O(α(n))
    unite(x, y): x と y を同じ集合にする。計算量はならし O(α(n))
    treeSize(x): x を含む集合の要素数。
*/
struct UnionFind {
    vector<int> size, parents;
    UnionFind() {}
    UnionFind(int n) { // make n trees.
        size.resize(n, 0);
        parents.resize(n, 0);
        for (int i = 0; i < n; i++) {
            makeTree(i);
        }
    }
    void makeTree(int x) {
        parents[x] = x; // the parent of x is x
        size[x] = 1;
    }
    bool isSame(int x, int y) { return findRoot(x) == findRoot(y); }
    void unite(int x, int y) {
        x = findRoot(x);
        y = findRoot(y);
        if (size[x] > size[y]) {
            parents[y] = x;
            size[x] += size[y];
        } else {
            parents[x] = y;
            size[y] += size[x];
        }
    }
    int findRoot(int x) {
        if (x != parents[x]) {
            parents[x] = findRoot(parents[x]);
        }
        return parents[x];
    }
    int treeSize(int x) { return size[findRoot(x)]; }
};
int main() {
    int N;            // the number of nodes
    int Q;            // the number of query
    vector<int> P;    // p is a "same" or "unite" command.
    vector<int> A, B; // a and b are nodes.
    cin >> N >> Q;
    UnionFind uft(N); // make trees
    for (int i = 0; i < Q; i++) {
        int p, a, b;
        cin >> p >> a >> b;
        P.push_back(p);
        A.push_back(a);
        B.push_back(b);
    }
    for (int i = 0; i < Q; i++) {
        if (P[i] == 0)
            uft.unite(A[i], B[i]);
        else if (P[i] == 1) {
            if (uft.isSame(A[i], B[i]))
                cout << "1\n";
            else
                cout << "0\n";
        }
    }
    return 0;
}

関連問題

AtCoder ABC 120 D – Decayed Bridges
union-find tree の逆をする問題。素集合系をどんどん分割していく。このようなときは、求められる答えと逆順に操作を行い、得られた結果を更に逆順に出力する。

参考

データ構造

Posted by cs-learner