C++で素集合データ構造（Disjoint Set）を実装する方法

素集合データ構造（Disjoint Set）とは、ある要素が複数の集合に同時に属することはない、互いに重ならない集合の集まりを表すデータ構造です。このデータ構造は、部分集合に対して「Union（結合）」と「Find（探索）」という2つの基本操作をサポートしており、グラフアルゴリズムにおける連結成分の管理やサイクル検出など、さまざまな場面で活用されています。

主な操作

Find()：要素の所属を調べる

特定の要素がどの部分集合に属しているかを調べ、その集合の代表元（根）を返します。

Union()：2つの集合を統合する

異なる2つの部分集合を1つの集合に統合します。統合後は、一方の集合の代表元がもう一方の代表元として機能します。

関数と擬似コード

素集合データ構造の基本的な流れは、以下の擬似コードのように表現できます。

Begin
    要素をkと仮定する
    makeset(k):
        k.parent = k
    Find(k):
        もし k.parent == k ならば
            return k
        そうでなければ
            return Find(k.parent)
    Union(a, b):
        集合aとbを入力として受け取る
        aroot = Find(a)
        broot = Find(b)
        aroot.parent = broot
End

makesetでは各要素が自分自身を親として持つ独立した集合を作り、Findでは親を再帰的にたどって根を見つけます。Unionは2つの要素の根を求め、一方の根の親にもう一方の根を設定することで集合を統合します。

C++での実装例

以下は、unordered_mapを使って親ポインタを管理するシンプルな実装例です。

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

class DisjointSet { // 素集合を表すクラス
    unordered_map<int, int> parent;
public:
    void makeSet(vector<int> const &wholeset) {
        // makeSet操作を実行
        for (int i : wholeset) // 各要素ごとに独立したn個の素集合を作成
            parent[i] = i;
    }

    int Find(int l) { // 要素lが属する集合の根を求める
        if (parent[l] == l) // l自身が根の場合
            return l;
        return Find(parent[l]); // 根が見つかるまで親を再帰的にたどる
    }

    void Union(int m, int n) { // 2つの部分集合mとnを統合する
        int x = Find(m);
        int y = Find(n);
        parent[x] = y;
    }
};

void print(vector<int> const &universe, DisjointSet &dis) {
    for (int i : universe)
        cout << dis.Find(i) << " ";
    cout << '\n';
}

int main() {
    vector<int> wholeset = { 6, 7, 1, 2, 3 }; // 全体集合の要素
    DisjointSet dis; // DisjointSetクラスを初期化
    dis.makeSet(wholeset); // 各要素に対して個別の集合を作成
    dis.Union(7, 6); // 7と6を同じ集合に統合
    print(wholeset, dis);

    if (dis.Find(7) == dis.Find(6)) // 同じ集合に属するかどうかを判定
        cout << "Yes" << endl;
    else
        cout << "No";

    if (dis.Find(3) == dis.Find(4))
        cout << "Yes" << endl;
    else
        cout << "No";

    return 0;
}

実行結果

6 6 1 2 3
Yes
No

出力の解説

初期状態では各要素が自分自身の根となっているため、makeSet直後の出力は「6 7 1 2 3」となります。しかしUnion(7, 6)によって7と6が同じ集合に統合されると、7の根は6になるため、出力は「6 6 1 2 3」となります。その後の判定では、7と6は同じ集合に属するため「Yes」、3と4は異なる集合に属するため「No」が出力されます。

なお、このシンプルな実装では木が偏って深くなる可能性があります。実用的には、経路圧縮（Path Compression）やランクによる統合（Union by Rank）を組み合わせることで、FindとUnionの計算量をほぼ定数時間（アッカーマン関数の逆関数オーダー）まで改善できます。