并查集总结
大部分摘自 数据结构并查集 - 洛谷专栏
带权并查集
可以在并查集的边上定义某种权值、以及这种权值在路径压缩时产生的运算，从而解决更多的问题。
经典题：P1196 [NOI2002] 银河英雄传说
最经典的关系就是用于维护这样的 类数轴上多点距离 类型的信息
办法就是，维护 “和根节点的相对距离（可能有正负
类似的还有：
- 维护倍数关系
- 维护是否是二分图（节点之间距离的奇偶性）
- 维护树上 / 基环树上简单路径代表的信息
拓展域并查集
经典题：P1892 [BOI2003] 团伙
不同于边带权的解法，我们这样解决关系传递：
从题目中我们不难得知要维护的东西比较多，
- 如果是朋友，就直接合并。
- 如果是敌人的话，我们需要注意题意：一个人的朋友的朋友是朋友，一个人的敌人的敌人是朋友。也就是说，假如
和 互相对立，那么 和 的敌人就是朋友，我们需要将 和 的敌人合并，同理，也要将 与 的敌人合并。
可以通过将
还有很多时候，这可以帮我们确认 “是否产生矛盾
可撤销并查集
可撤销并查集是一种扩展了标准并查集数据结构的数据结构，它允许在进行 merge 和查询 find 操作的同时，能够 undo 或者撤销之前的操作。
这种数据结构通常用于支持一些需要回滚操作的应用，比如在离线算法中或者需要进行回退的决策问题中。
当然主要是应用于在线算法，因为离线算法反悔可以完全输入后在一起处理。
当然，启发式合并或者按秩合并这两种合并方式对于并查集来说是没有用影响的。
因此，用栈来记录每次合并的操作，然后进行对
用栈来记录每次合并的操作。
每次的操作往里放，先进去的会被晚撤销，撤销的一定是最近的这一步。
维护若干 引用 - 数值 对，表示每次修改之前这个变量的数值，到时候弹栈恢复即可
可删除并查集
你需要写一个数据结构实现以下三种操作 1: 合并 x,y 所在的集合。 2: 把 x 移到 y 所在的集合。 3: 求 x 所在集合元素个数与元素和。
我们并不可以通过 merge 操作直接将 x 添加到 y 所在的集合。
因为如果我们直接 merge 的话，x 的子节点也会与 x 一同并入 y 的集合。
我们可以通过给每个元素设置一个虚拟父节点，每次移动的时候操作的是实际的节点，而不是父节点即可完成。
因为这个时候操作的节点都是叶子节点，不会有副作用。
如果 x 点没有儿子就可以直接做。然后发现不管是 1 的合并还是 2 的直接移动都是直接接在根上的。
换言之只要每个集合的根节点不可能作为 x 点出现那么每次 2 操作就可以直接移动。
但是题目中 x 可以是任何一个点。因此你的集合的根节点不应该是 1…n 的任何一个点。对于每个集合的根，都应该是一个虚点。
方便起见我们把这 n 个虚点设置成了 i + n 的形式。
可持久化并查集
你需要写一个数据结构实现以下三种操作 1: 合并 x,y 所在的集合。 2: 回到第 k 次操作（执行三种操作中的任意一种都记为一次操作）之后的状态
3: 询问 x 与 y 是否在同一个集合内。 ； 。
可持久化并查集是建立在可持久化数组上的，在学习可持久化并查集之前，需要先学习可持久化权值线段树，权值线段树。
众所周知，并查集有两种优化方式：
- 路径压缩
- 按秩合并
我们的并查集的
因为每个版本的并查集的结点深度可能是不一样的，所以我们还需要要新开一个可持久化数组来记录每个版本的 dep 数组。
其实本质上就是俩可持久化数组，一个存 dep 一个存 fa
并查集的各种应用
1、并查集维护联通块信息
2、并查集生成树
- 将每次合并两个集合的元素关系
加入生成树，最后得到一棵树（或森林 ） ，
3、并查集离线（线段树分治）
- 需要用到可撤销并查集
4、并查集与序列位置操作
- 处理不改变顺序的序列上的连续区间相关问题，可以使用并查集来维护相关信息
5、并查集联通块与序列操作
- 给出三个序列
，求出 的最大值 - 按权值从大到小考虑
，即枚举 “区间最小值为 的极大区间” 的同时维护其上的 的最大值，每次枚举更新答案即可 - 类似以上考虑 “不可逆的融合” 来不遗漏考虑所有情况的方法，可以借助并查集实现
- 此方法不一定只能用于序列，一些具有类似性质的树上问题也可以应用