有关并查集的两篇文章觉得还不错：

 https://blog.csdn.net/yuanmartin/article/details/108489016

https://blog.csdn.net/m0_50966319/article/details/124252266

#include <iostream>
#include <vector>
using namespace std;

const int len = 1005;

// fa[i] 表示节点i所在集合的根节点是什么。
int fa[len];

// size[i] 表示节点i所在集合的节点数目。好想没什么用，因为不一致。
int _size[len];

// 图中连通分量的数目。这里每个集合就是一个连通分量
int cnt;

/*
    功能：找出节点x所在集合的根节点。
*/
int _find(int x){
    if(fa[x] == x){
       return x;
    }else{
        // 路径压缩
        fa[x] = _find(fa[x]);
    }
    return fa[x];
}

/*
    功能：将节点x和节点y所在的两个集合合并成一个集合。
*/
void _union(int x, int y){
    int fx = _find(x);
    int fy = _find(y);

    if(fx == fy){
        return;
    }

    if(_size[fx] <= _size[fy]){
        // 按秩合并。即将小集合合并到大集合里
        fa[fx] = fy;
        _size[fy] = _size[fy] + _size[fx];
        // 连通分量减一
        cnt--;
    }else{
        // 按秩合并。即将小集合合并到大集合里
        fa[fy] = fx;
        _size[fx] = _siz...