C++ set在并查集實現中的應用

在并查集（Disjoint Set）中，C++中的set容器可以用來實現集合的合并和查找操作。并查集是一種數據結構，用于處理不相交集合的合并和查詢問題。

在C++中，set容器是一個有序的集合，可以用來存儲數據，并且能夠快速查找和插入元素。在并查集實現中，可以使用set容器來存儲每個集合的元素，并使用find()函數來查找元素所屬的集合。

下面是一個簡單的示例代碼，演示了如何使用set容器來實現并查集：

#include <iostream>
#include <set>
#include <unordered_map>

using namespace std;

class DisjointSet {
public:
    void makeSet(int x) {
        parent[x] = x;
        rank[x] = 0;
        sets[x].insert(x);
    }

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

    void unionSets(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            if (rank[rootX] < rank[rootY]) {
                swap(rootX, rootY);
            }
            parent[rootY] = rootX;
            sets[rootX].insert(sets[rootY].begin(), sets[rootY].end());
            sets.erase(rootY);
            if (rank[rootX] == rank[rootY]) {
                rank[rootX]++;
            }
        }
    }

    bool sameSet(int x, int y) {
        return find(x) == find(y);
    }

private:
    unordered_map<int, int> parent;
    unordered_map<int, int> rank;
    unordered_map<int, set<int>> sets;
};

int main() {
    DisjointSet ds;

    ds.makeSet(1);
    ds.makeSet(2);
    ds.makeSet(3);

    ds.unionSets(1, 2);
    ds.unionSets(2, 3);

    cout << "Is 1 and 3 in the same set: " << ds.sameSet(1, 3) << endl;

    return 0;
}

在上面的示例代碼中，我們定義了一個DisjointSet類，其中使用了unordered_map來存儲每個元素的父節點和秩（rank），并使用set來存儲每個集合的元素。通過makeSet()、find()、unionSets()和sameSet()函數實現了并查集的基本操作。

通過使用set容器，我們可以高效地實現并查集的合并和查找操作，使得對不相交集合的操作更加方便和高效。