并查集 学习笔记

模板及讲解

一份资料

拆点

把一个点拆成两个点比较简单不多说

带权

并查集维护一个$r$数组,表示$i->father(i)$的权值。
定理:一个并查集中从一个点出发,沿着它所指向的边一直走,并累加下路上的权值(如果边是反的那么就取权值的负数),走一圈回来,累加的和模 最大值$+1$ 结果一定是$0$
路径压缩:
Markdown
由图,根据敌人的敌人是朋友(多于两个阵营不适合带权并查集),新的$r_x$的值就是$(r_x+r_{f_r})\%(MaxWeight+1)$

合并的情况:$father(y)=x$,$x$是$a$的根,$y$是$b$的根
Markdown

由图,$(k+r_b+r_y-r_a)\%(MaxWeight+1)=0$,因为$y$合并至$x$,所以$r_y$变了,那么我们就算出$r_y$即可,$r_y=(-k-r_b+r_a+MaxWeight+1)\%(MaxWeight+1)$,其中加上$MaxWeight+1$是为了防止负数。
查询的情况(在一个集合)
Markdown

由图,如果$(k+r_b-r_a+MaxWeight+1)\%(MaxWeight+1)=0$的话,那么$a->b$就是$k$,我们就可以这样判断关系。

维护数组(维护差分约束)

在$find$时,先递归$t=find(f(x))$,然后维护值,然后再使$f(x)=t$
差分约束:用并查集维护$c_i=s_i-s_{rt}$

常见题型

1、直接使用
Q: 询问无向图连通性问题
解; 直接使用
例题: Hdu 2874
2、拆点
例题: NOIP2010 T3
3、带权并查集
例题: NOIP2010 T3
4、维护数组(差分约束)
Q: 约束区间$[l, r] = v$
解: 用并查集维护$c_i=s_i-s_{rt}$
例题: BZOJ 1202

相关代码

------ 本文结束 ------