并查集套用码

class Djset {

private:

    vector<int> parent;  // 记录节点的根

    vector<int> rank;  // 记录根节点的深度（用于优化）

    int count;        // 记录连通分量的个数

    int rest;          // 记录多余的连接数

public:

    Djset(int n): parent(vector<int>(n)), rank(vector<int>(n)), count(n), rest(0) {

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

    }

   

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

            count--;

        } else {

            rest++;

        }

    }

    int getCount() {

        return count;

    }

    int getRest() {

        return rest;

    }

};