并查集

并查集重要的是路径压缩。并查集的题感觉都不简单。。。

因为往往还要维护额外信息，难度就上去了。。。

对于 $parent[N]$ 数组，初始化时全部指向自己。

for(int i = 1; i <= n; ++i)
    parent[i] = i;

带有路径压缩的 $find(val)$ 函数

int find(int val)
{
    if(val != parent[val])
        parent[val] = find(parent[val]);
    return parent[val];//返回所在集合的“祖宗节点”
}

合并两个集合的操作

合并操作首先应该判断两元素是否已经同属一个集合；之后在考虑将其中一个集合接到另一个集合中去。

if(order[0] == 'M')//如果为合并操作
{
    if(find(a) == find(b)) continue;
    parent[find(a)] = find(b);//把集合a的祖先节点接在集合b的祖宗节点下
}

并查集的经典应用：最长连续序列(LeetCode128.最长连续序列)

这题我真没想到是并查集，看了标签才知道可以用并查集解决。

主要思路是：

• 1. 判断当前 $val$ 是否出现过，出现过则直接 $continue$ ，否则进入后续判断；
• 1. 因为没有出现过，当前 $val$ 按照并查集的初始化方式，自己一个值构成一集合，且集合中元素只有自己一个；
• 1. 查询 $val - 1$ 是否出现过，若出现过，则合并 $val - 1$ 和 $val$ 两个所在的集合；
• 1. $ val + 1 $ 同理。
• 1. 利用 $find()$ 函数查询 $val$ 的父节点及其所在集合的大小，结果即为含有当前 $val$ 的最长连续序列的长度。

还有一道食物链的题目，要求并查集同时维护一个到祖宗节点的距离。