并查集有普通并查集,拓展域并查集,带权并查集这几种.
所有并查集的初始化都是初始爹都是自己.
并查集支持路径压缩和按秩合并两种合并方法.
路径压缩
由于路径压缩是查询的时候顺带压缩了一下,时间复杂度比较玄学,但是肯定比 $O(\log n)$ 要低.
按秩合并
并查集的另一种合并操作就是按秩合并,这样的并查集会因为一个size而控制树高不会超过 $\log n$ 的高度.
而且,这样的合并是一开始就写好固定了的,也就是支持可持久化(使用主席树维护即可)
普通并查集
一个元素的父节点变成另一个元素.用于检查某些元素在不在一个集合里面.
并查集支持维护区间,用法是一段序列的头和更靠右的合并,保证区间末尾一定是并查集的头,这样可以保证时间复杂度O(n),因为每一个数最多被合并一次.
拓展域并查集(种类并查集)
就是有两个及以上的并查集一起操作.比如,要求原有朋友关系的基础上添加一种新关系叫敌人关系,满足”敌人的敌人是朋友”,就可以拓展一个并查集,开到二倍空间.
实战就是,假设A和B是敌人,就合并A+n和B+n,假如B原先有敌人了那就合并朋友一个人和他敌人的敌人.
敌人本质上还是一个并查集.
带权并查集
并查集加个权重.比较灵活,维护的东西也比较多变,不好讲.
举例:给哪个学生比哪个学生多考几分,问谁和谁之间的分数差,就可以维护并查集叶节点和根节点的分数差关系.
魔改并查集
有的时候会让写一种奇怪的数据结构,支持某个节点的孩子并到节点的爹那里,同时后续操作还可能让某些节点继续并到该节点.
这类题的特征是:
- 支持查询一个节点的爹
- 盒子装球,合并盒子之后一个是空的,于是接着装球
我们把所有节点都看作一个点,于是他就是普通并查集.但是如何解决空盒子的问题?
建立一个映射,在并查集上动态开点,标记新开的点是原来被合并的点即可. 同时size啥的就很好维护了.
实战
p5937,维护一个01组成的序列,给定一个区间,请你判断以下话语的正确性.如(1 2 odd 3 4 even)给定区间首尾.
对于区间的题考虑如下转化:
区间[l,r]可以转化为区间[0,l-1]和区间[0,r]的性质.
然后再由于奇偶性的传递可以维护一个种类并查集.NOI食物链问题:
维护三个并查集，表达的是吃与被吃的关系.
如何表达他们是同级的呢？A不吃B而且B不吃A，或者直接查他们是不是一个集合
如何表达吃的关系呢？直接维护并查集，A吃B抽象成A的上级就是B+n(不同群系，不同并查集)
这样就得到了一个循环的样子：群系ABC三个并查集，同级就直接合并
吃的关系就opt1合并opt2+mxx表示A群系的opt1和opt2+mxx是一级的，由于opt2+mxx是B群系所以体现了opt1吃opt2
注意初始化并查集直接原数存就好
注意先判断是不是真话再合并防止出现环的情况ATabc279f 盒子,写一个程序支持维护以下操作:1把一个新球放到某个盒子里2把a盒子里面的所有球放到b盒子里面3查询某个球属于某个盒子.
并查集维护,关于某个盒子放到另一个盒子里面的情况可以通过开点的方法解决.(注意,点和箱子都应该看成点)