素集合

素集合(Disjoint set)

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

目次

{{ $t('Class') }}

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

  • コンストラクタに要素の数を渡して初期化する.初期状態ではすべての要素がそれぞれの集合をなす。
  • sameで2つの要素が同じ集合に属するかどうかを判定する.
  • uniteで2つの要素が含まれる集合を統合する.
 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
class DisjointSet {
public:
    DisjointSet(int n) {
        rank.resize(n);
        parent.resize(n);
        for (int i=0; i<n; i++) rank[i] = 0, parent[i] = i;
    }

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

    void unite(int x, int y) {
        x = root(x), y = root(y);
        if (rank[x] > rank[y]) {
            parent[y] = x;
        } else {
            parent[x] = y;
            if (rank[x] == rank[y]) rank[y]++;
        }
    }

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

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

        return parent[x];
    }
};

{{ $t('Usage') }}

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

 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;
}