并查集

算法过程:(路径压缩)
1.最开始每个人都是自己的父亲节点
2.递归找根节点. (非递归也可)
如果f[x] != x(不是根节点)
f[x] = getf(f[x]); -----路径压缩
否则
返回 x;
3.查询x,y是否在同一个集合.
3.1 先找出x,y所在集合的两棵树的根节点.fx,fy(擒贼先擒王原则)
3.2 判断fx == fy
3.2.1(真) 返回真.
3.2.2(假)
3.2.2.1 将fy的父节点变为fx (靠左原则)

解释:
①代码看Kursal算法模板.
②复杂度:O(logn)
数学分析:https://blog.csdn.net/wang3312362136/article/details/86475324

二.按秩合并(又称启发式合并)
思路:
给每个点一个秩，其实就是树高
每次合并的时候都用秩小的指向秩大的，可以保证树高最高为log2(n).
操作的时候，一开始所有点的秩都为1
在一次合并后，假设是点x和点y，x的秩小
当然x和y都是原来x和y所在区间的顶点
设点x秩为rank[x]
将fa[x]指向y，然后将rank[y]的与rank[x+1]取max
因为rank[x]为区间x的高，将它连向y之后，y的树高就会是x的树高+1，当然也可能y在另一边树高更高，所以取max

合并代码:

x=getf(x);y=getf(y);
if(x!=y)
{
    if(rank[x]<=rank[y])
        {
           fa[x]=y;
            rank[y]=max(rank[y],rank[x]+1);
        }
    else 
        {
              fa[y]=x;
              rank[x]=max(rank[x],rank[y]+1);
         }
}

带权并查集:(待补)