并查集 学习笔记

模板及讲解
一份资料
1 拆点
把一个点拆成两个点比较简单不多说

2 带权
并查集维护一个$r$数组,表示$i->father(i)$的权值。
定理:一个并查集中从一个点出发,沿着它所指向的边一直走,并累加下路上的权值(如果边是反的那么就取权值的负数),走一圈回来,累加的和模 最大值$+1$ 结果一定是$0$
合并的情况:$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$,我们就可以这样判断关系。

3 维护数组(维护差分约束)
在$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

相关代码

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