并查集-一一网

定义

并查集是一种树形的数据结构，顾名思义，它用于处理一些不交集的合并及查询问题。它支持两种操作：

查找（Find）：确定某个元素处于哪个子集；
合并（Union）：将两个子集合并成一个集合。

背景

通俗地讲一个故事：几个家族进行宴会，但是家族普遍长寿，所以人数众多。由于长时间的分离以及年龄的增长，这些人逐渐忘掉了自己的亲人，只记得自己的爸爸是谁了，而最长者（称为「祖先」）的父亲已经去世，他只知道自己是祖先。为了确定自己是哪个家族，他们想出了一个办法，只要问自己的爸爸是不是祖先，一层一层的向上问，直到问到祖先。如果要判断两人是否在同一家族，只要看两人的祖先是不是同一人就可以了。

结构

并查集本身术语树状结构，通常使用数组来表示，每个节点记录自己的父节点是谁

每次跟根比较，满足条件则加入当前集合

使用三部曲

初始化

初始化时创建一个元素个数相同的数组，用来表示元素i的父节点是谁，并出示化为自身，及初始状态下每个元素的父节点都是自己

int fa[MAXN];
void init(int n){
    for (int i = 1; i <= n; ++i)
        fa[i] = i;
}
复制代码

查询

使用递归，逐层访问父节点，直至找到根节点，如果需要判断2个元素是否术语同一个集合，只需要看根节点是否相同

int find(int x){
    if(fa[x] == x)
        return x;
    else
        return find(fa[x]);
}
复制代码

合并

将一个元素或一组元素，加入到当前树中，只需要将需要加入的元素的父节点设置为当前节点即可

注意这里是两个元素的跟相互merge，而不是元素本身

void merge(int i, int j){
    fa[find(i)] = find(j);
}

// 是不对的
void merge(int i, int j){
    find(i) = j;
}
复制代码

路径压缩

如果一直向其中添加元素，树结构将变得很长，找寻节点将变得非常耗时，这是可以使用路径压缩，将树的结构扁平化

int find(int x){
    if(x == fa[x])
        return x;
    else{
        fa[x] = find(fa[x]);  //父节点设为根节点
        return fa[x];         //返回父节点
    }
}
复制代码