并查集学习笔记

并查集学习笔记

本质上还是一个复习笔记。

考虑这样一个问题：

• 给出 \(x,y\) ，合并 \(x,y\) 所在集合。

• 给出 \(x,y\)，查询 \(x,y\) 是否在同一集合内。

我们把集合当成一棵树，两个点有连边就表示他们在同一个集合内。这棵树的根节点就是这个集合的 “老大”，也就是这个集合里面的第一个数。

我们定义 \(fa[x]\) 表示 \(x\) 所在集合的“老大”，初始的时候 \(fa[x]=x\)。

对于第二个操作，问 \(x,y\) 是否在同一集合以内，那么就是我们找到 \(x,y\) 的所在树“老大” 是否相同即可。

找到这个“老大”的方法就是我们对当前节点 \(x\) 不断找 \(fa[x]\)，一直到找到一个 \(y\)，使得 \(y=fa[y]\) 即可，也就是根节点。

如果要合并两个 \(x,y\) 集合，我们直接把 \(fa[x]=y\) 即可。

但是按照这样的方法，如果这棵树是链的话，每次查询最坏要 \(O(n)\) 的时间。

考虑路径压缩，也就是我在进行查询操作的时候，我在路径上的所有节点的“老大”最终都应该是根节点，所以找到根节点后我们在回溯的时候把这条路径上所有点的 \(fa\) 值都赋值为这个根。

这样可以减少递归次数，下一次查询他的时候就可以直接跳到这个根而不是一层层跳。

这样的时间复杂度近似于 \(O(1)\)。

带权并查集

其实就是在路径合并的时候顺便维护一些题目要求维护的东西。

P1196 [NOI2002] 银河英雄传说

这一类题指向性都比较强，都有“合并”“在同一集合内”这样的标志。

考虑维护这样两个信息：

• 给出 \(x,y\)，表示合并 \(x,y\) 所在集合。
• 给出 \(x,y\)，问 \(x,y\) 之间点的数量。

考虑维护两个东西 \(sum_x\) 表示 \(x\) 到根的距离，\(cnt_x\) 表示 \(x\) 底下的节点个数。

其他的就比较容易想了，具体可以看代码：

\(Code\)