并查集

并查集是一种常被用来解决分组问题的算法

主要有两种操作

• 并 （合并两个不同的集合）
• 查 （查找元素的大哥）

每个元素都有一个大哥，对应数组num[k]的值，k是当前元素，num[k]是k的大哥

初始时每个元素的大哥都是元素本身，即num[k]=k

大哥的大哥也是你的大哥，就相当于大哥带着你投奔别人了

那么如何去找一个元素的大哥呢？代码如下

int find(int x){
    if(x==num[x])//该元素的大哥就是元素本身
        return x;
    else
        //通过前面的判断可知,x的大哥不是它本身,所以就要去寻找x的大哥,那目前x的大哥是不是num[x]
        //那万一大哥的大哥不是它本身怎么办，所以要递归去寻找大哥的大哥，并把大哥赋值给小弟
        return num[x]=find(num[x]);
    
    //最后返回大哥即可
    return num[x];
}

合并操作代码

void merge(int x,int y){
    //这里调换 x y 的位置都可以
    //找到所有 x 的所有大哥都拜 y 的大哥为大哥
    num[find(x)]=find(y);
}