并查集學(xué)習(xí)可查看網(wǎng)站

class Djset {
public:
    vector<int> parent;  // 記錄節(jié)點(diǎn)的根
    vector<int> rank;  // 記錄根節(jié)點(diǎn)的深度（用于優(yōu)化）
    Djset(int n): parent(vector<int>(n)), rank(vector<int>(n)) {
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }

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

    bool merge(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;
            if (rank[rootx] == rank[rooty]) rank[rootx] += 1;
            return false; // 根節(jié)點(diǎn)不同，返回false
        }
        // 根節(jié)點(diǎn)相同，返回true
        return true;
    }
};