并查集小结

· · 个人记录

简单，高效的数据结构。

即把一条链上的全部点的父亲压缩成为这条链的终点

可以大大省略时间，但是会丢失一些信息

如果想知道本来的父亲以求出 LCA 等，可以使用——

此方法是非路径压缩并查集的时间补偿方法。

一个有趣的地方是，每次 merge 是只要我们把小的树安置在大的树上，而不是反着操作，可以大幅减小树深，从而减小每次一步一步查询的时间。

这里的小的有多种定义，如树深小，子树小等。

可以证明按秩合并后单次查询时间复杂度不超过 \log_2n。

对于每个点建立一个虚拟节点（可以形象的称之为“母亲”），默认母亲等于自己。

注意，之后我们的并查集维护的都是母亲而不是本身。

当我们需要删除一个点的时候，我们就可以“离家出走”脱离原来的母亲。

如果我们需要将这个点加入新的树，我们就可以把这个点的母亲设为新的“家庭”上的任何一个母亲。

该方法建立于按秩合并基础上。

其实很简单，将被合并的节点加入一个栈里面，撤销时弹出栈，将父亲设为自己即可。

该方法建立于按秩合并基础上。

维护一个时间戳数组，记录当前节点与它的父亲建立联系的时间。

查找 x,y 什么时候联通，就相当于查找 max_{i\in x\to y}\ time_i。

利用父亲信息，跑一遍 LCA 维护答案即可。