$\Huge\color{orchid}{点击此处获取更多干货}$

并查集

基本原理在此
并查集的直接应用场合就是统计无向图连通分量的数量和大小，可以直接沿用之前的UnionFind类，并且在此基础上稍加修改。代码部分会详解，并带入本次针对“并”操作的改进方法：按秩合并

C++ 代码

定义：

class UnionFind {
private:
    int* origin;    //跟之前一样
    int* size;      //统计每个元素所在集合的大小
    int* rank;      //统计每个元素的秩（之后会细说）
    int cnt;        //统计集合总数
public:
    //构造、析构函数略微不同
    UnionFind(int n);

    //find函数不用再压缩路径了
    int find(int e);

    //unite函数，带有按秩合并的改进
    void unite(int x, int y);

    //新增加的，查找连通分量大小和数量
    int getSize(int e);
    int getCount();
};

构造函数中需要初始化rank和size表。每个元素自成集合时，大小都是1。秩的含义就是对应到树结构中，以该元素对应的节点为根的子树高度（从0开始计算）

UnionFind::UnionFind(int n) {
    cnt = n;
    origin = new int[n];
    iota(origin, origin + n, 0);
    rank = new int[n];
    fill(rank, rank + n, 0);
    size = new int[n];
    fill(size, size + n, 1);
}

UnionFind::~UnionFind() {
    delete[] origin, rank, size;
}

有了按秩合并，路径压缩就不是必要的了，当然两者不冲突，可以沿用之前的，也可以像现在这样，直接按照origin表找到代表元素

UnionFind::find(int e) {
    while(e != origin[e]) {
        e = origin[e];
    }
    return e;
}

合并总是让一个集合的代表元素成为另一个集合的源，但是此处的“另一个”集合中，所有元素在被合并过去的时候，对应的秩都要+1，意味着查找的时候需要多一次循环，因此让秩更大的代表元素成为秩更小的代表元素的源，能让查找的时候效率更高。

void UnionFind::unite(int x, int y) {
    int pr = find(x), nx = find(y);
    if(pr == nx) {
        return;
    }
    if(rank[pr] > rank[nx]) {
        swap(pr, nx);   // 秩小的合并到秩大的上面
    }
    origin[pr] = nx;
    size[nx] += size[pr];   //合并之后pr所属元素已经全部属于nx，集合大小需要累加
    if(rank[pr] == rank[nx]) {
        rank[nx]++;     //两秩相同时，合并成为的新集合，对应的树高比原先大1
    }
    cnt--;
}

统计连通分量数量和大小就很显而易见了

int UnionFind::getSize(int e) { return size[e]; }

int UnionFind::getCount() { return cnt; }