当前位置: 首页 > >

并查集 详解补集法

一、为什么要用补集法
1、此补集非数学上的补集,这是一个类似”关系”的东西,有几个关系就有几个补集。
2、解释一下,从用法上讲,并查集一般会维护集合内的点有关系,或有什么关系。比如关押罪犯这道题就维护二个点有(不在同一监狱)的关系,那么相对应的,就会有一个“反集”表示二者在同一关系。正反集就代表正反这两种关系(即并查集维护“有什么关系”,就会存在没有这种关系的补集)。
而比如食物链这道题,并查集维护的是有关系,具体有什么关系呢,根据题意,每个点与其他的点都有“没关系”“被捕食”“捕食”三种关系,因此就有三个补集
3、其实由此我们就可以看出,补集实际上就是多个并查集,有x个补集相应的就可以维护x+1个并查集来解决,不过显然是补集比较方便好写
4、从算法讲,它是基于并查集无法维护点到根节点的距离这个问题而存在的。要解决这个问题,就要先了解一下问什么这个问题会存在。
5、很显然,是路径压缩导致并查集中的点失去了与父亲的联系,即无法维护其到根节点的距离(因为直接连在了根节点上了)。这会导致一些(一点都不)隐蔽的错误,比如两个点有联系了,此时他们的父亲本来也已经可以建立关系了,由于路径压缩他们就不会建立联系。


二、补集法的使用方法
实现过程就是把集合数组par[]开x大倍,x为补集数
1、初始化要从1 到 n+x*n
for(int i=1;i<=n+x*n;i++)
par[i]=i;
2、合并时
(1)注意同一集合要分别在各自的补集内进行
un(u,v);
un(u+n,v+n);
un(u+2*n,v+2*n)

un(u+x*n,v+x*n);
(2)如果是不同集合之间的合并(一个集合与另一集合存在联系),则合并不同补集
un(u,v+n);
un(u+n,v+2*n);

un(u+x*n,v);
注:上述代码只是举个例子,具体问题需具体分析


三、如果不想用补集怎么办
其实也有两种办法
1、dis[]维护距离法
我们知道,并查集不能维护距离,那么我们为什么不能专门维护距离呢。基于这种思想,我们可以维护一个数组dis[]来记录当前点到根节点的距离。


(未完待续~)



友情链接: year2525网 工作范文网 QS-ISP 138资料网 528200 工作范文网 baothai 表格模版