素集合

素集合(Disjoint set)

素集合(Disjoint set)の実装方法を紹介します.
Feb. 2, 2020, 1:51 p.m.

更新履歴

更新日時 更新内容
実装を単純化して集合の要素数を取得するsizeメソッドを追加しました。

目次

インターフェイス

要素の重複のない複数の集合を管理するDisjoint Set(Union-Find)というデータ構造.

  • コンストラクタに要素の数を渡して初期化する.初期状態ではすべての要素がそれぞれの集合をなします。
  • bool same(int x, int y)で2つの要素が同じ集合に属するかどうかを判定します。
  • unite(int x, int y)で2つの要素が含まれる集合を統合します。
  • long long size(int n) - nが含まれる集合の要素数を返します。

実装

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class DisjointSet {
public:
    DisjointSet(int n) {
        rank.resize(n);
        parent.resize(n);
        sizes.resize(n);
        for (Int i=0; i<n; i++) rank[i] = 0, parent[i] = i, sizes[i] = 1;
    }

    bool same(int x, int y) {
        return root(x) == root(y);
    }

    void unite(int x, int y) {
        x = root(x), y = root(y);
        if (x == y) return;
        if (rank[x] < rank[y]) swap(x, y);
        else if (rank[x] == rank[y]) rank[x]++;
        parent[y] = x;
        sizes.at(x) += sizes.at(y);
    }

    long long size(int x) {
      return sizes.at(root(x));
    }

private:
    vector<int> rank;
    vector<int> parent;
    vector<long long> sizes;

    int root(int x) {
        if (x != parent[x]) {
            parent[x] = root(parent[x]);
        }

        return parent[x];
    }
};

使用例

無効グラフに閉路が含まれるかを判定する.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
struct Edge { int src, dst; };

bool hasCycle(vector<Edge> &edges, int n) {
    DisjointSet ds(n);

    for (auto edge: edges) {
        if (ds.same(edge.src, edge.dst)) {
            return true;
        }

        ds.unite(edge.src, edge.dst);
    }

    return false;
}


int main(void) {
    vector<Edge> edges;
    edges.push_back({ 0, 1 });
    edges.push_back({ 1, 2 });
    edges.push_back({ 2, 0 });
    if (hasCycle(edges, 3)) cout << "yes";
    else cout << "no";
    cout << endl;
}