集训队讲座第十讲——并查集的深化与扩展.ppt

1、ACM程序设计,杭州电子科技大学朱维聪hdu_zwc,集训队讲座-第十讲,并查集的深化与扩展(Merge_Find_Set),Index,1：并查集的概念。,2：并查集的优化。,3：并查集的扩展。,4：并查集的应用：LCATarjan算法。,5：区间最优值RMQ算法。,概念与实现方式,概念：并查集不相交集合每棵树一个集合,根为集合标识。树的形态并不重要,重要的是有哪些节点实现方式：一维数组的“森林表示法”。几个定义：祖先，父亲，子孙,生活中的集合,并查集的基本操作,MakeSet(x)：建立一个新集合x。x应该不在现有的任何一个集合中出现。Find(S,x)：返回x所在集合的代表元素。Merg

2、e(x,y)：把x所在的集合和y所在的集合合并。,不可忽视的弊端：无法高效的找寻儿子节点！,并查集的优化,1：启发式并查集：让深度较小的树成为深度较大的树的子树2：路径压缩：找到最久远的祖先时“顺便”把它的子孙直接连接到它上面,启发式并查集,1,5,6,4,维护一个dep数组记入元素代表的有向树的深度。每次合并操作将深度较小的集合合并到深度较大的集合中，并维护dep数组。,2,3,7,Dep1=2,dep4=3,启发式并查集,boolMerge(intx,inty)x=find(x);y=find(y);if(x!=y)returnfalse;if(depxdepy)treey=x;elset

3、reex=y,depy+;returntrue;,路径压缩,4,9,6,11,1,10,8,12,20,21,16,6,12,1,8,21,16,11,20,9,10,4,路径压缩的实现,递归式：intfind(intx)if(treex=-1)returnx;returntreex=find(treex);,路径压缩的实现,非递归式：intfind(intx)r=x;while(treer!=-1)r=treer;i=x;while(i!=r)j=treei;treei=r;i=j;returnr;,复杂度分析,并查集进行n次查找的时间复杂度是:O(n*)！可以看做一个小于5的常数K，所以进

4、行一次并查集操作的时间复杂度为：O(K)!,小试身手,Supermarket(POJ1456),Supermarket,Input:4502101202301Output:80,思考一下,解题小技巧！,1：看数据量，估测复杂度。2：思考如何将实际题目与集合的概念联系起来。3：如何建立模型，如何用查找合并两大操作来完成题目所要实现的动态过程。,解题的关键贪心思想！,思考！该如何贪心？,证明贪心思想的正确性！,给出一种贪心方法,1：按价值从大到小排序。2：对于每个商品，选择它目前为止能到达的最靠后的时间卖出。,复杂度估计,并查集解决！,并查集解决,黄色：已被占用；绿色：等待被占用；粉红：已经无法使

5、用，跳出。,节点的删除Junk-MailFilter,最初每个元素都属于自己的集合MXY：合并X所在的集合和Y所在的集合SX：把X从它所在的集合里删除请问：最后的集合个数？,方法：“找替身”,黄色：真身绿色：替身,实现方法,处理一个n=5的可删除节点的并查集：,求元素的个数VirtualFriends,Input：13FredBarneyBarneyBettyBettyWilma,Output：234,添加变量：,记变量cnti表示以i为代表元素的集合的元素个数。注意：该变量只对祖先节点有效，非祖先节点的cnt没有实际意义。,如何更新cnt数组,初始化每个集合的元素个数为1。当进行元素查找时，

6、不做任何处理。当进行集合合并时，将被合并的集合的元素个数叠加到合并后的大集合中。,注意：区分此处cnt数组和启发式并查集中dep数组。,合并过程,1,7,10,3,2,4,11,9,6,5,8,11,10,8,9,7,1,6,4,3,2,5,cnt1=5,cnt6=6,cnt6=11,红色节点的cnt数组有效！,再次深入：带权值的并查集,食物链,食物链,动物王国中有三类动物A,B,C，这三类动物的食物链构成了有趣的环形。A吃B，B吃C，C吃A。现有N个动物。每个动物都是A,B,C中的一种，但是我们并不知道它到底是哪一种。有人用两种说法对这N个动物所构成的食物链关系进行描述：第一种说法是1XY，

7、表示X和Y是同类。第二种说法是2XY，表示X吃Y。此人对N个动物，用上述两种说法，一句接一句地说出K句话，这K句话有的是真的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。1）当前的话与前面的某些真的话冲突，就是假话；2）当前的话中X或Y比N大，就是假话；3）当前的话表示X吃X，就是假话。你的任务是根据给定的N（1=N=50,000）和K句话（0=K=100,000），输出假话的总数。,试着来分析一下,1：如何来构造集合？2：如何来判断是否冲突？3：如何来记入信息？,困惑：表示元素之间的关系并且高效的查找,记入树中每个孩子节点到父亲节点的距离！,定义height变量,h

8、eightA%3=0：A与根节点是同类。heightA%3=1：根吃A。heightA%3=2：A吃根。,用TreeB=A来表示：A吃B,保存有效信息,Input:100711011212223233113231155Output:3,1XY:表示X和Y是同类。2XY:表示X吃Y。,1,2,3,height1=0,height2=1,height3=1,1,2,3,height1=0,height2=1,height3=2,判断信息的正确性,当输入为1XY时？当输入为2XY时？,抓住本质！不同的输入，相同的处理！,回想/父亲节点intheight;/到父亲的距离intdep;/有向树的深度in

9、tcnt;/集合的元素个数intFind(intx)boolMerge(intx,inty)voidDelete(intx)treeMAXN;,综合练习1：银河英雄传说,银河英雄传说,宇宙历七九九年，银河系的两大军事集团在巴米利恩星域爆发战争。泰山压顶集团派宇宙舰队司令莱因哈特率领十万余艘战舰出征，气吞山河集团点名将杨威利组织麾下三万艘战舰迎敌。,Mij：让第i号战舰所在的整个战舰队列，作为一个整体（头在前尾在后）接至第j号战舰所在的战舰队列的尾部。Cij：询问电脑，杨威利的第i号战舰与第j号战舰当前是否在同一列中，如果在同一列中，那么它们之间布置有多少战舰。,逐步分析各个击破,集合的概念体现

10、在哪里？Mij的处理方法？Cij的处理方法？需要用到哪些并查集的特征变量？合并时，这些变量该怎样更新？,定义变量：,fatheri:排在战舰i前面且相邻的战舰。heighti:战舰i到战舰fatheri之间的战舰的数量。cnti:战舰i所属队列的后方(包括i)的战舰数量。(该数组只对首战舰有效！),综合练习2：Exclusive-OR,另类的并查集,ConnectionsinGalaxyWar,方法：把所有数据都保存下来，然后倒着处理。对于提出的问题：及时回答，保存答案。对于删去的树枝：做并查集的合并处理。,运用：最近公共祖先LCA,概念：LeastCommonAncestors对于有根树T的

11、两个结点u、v，最近公共祖先LCA(T,u,v)：询问一个距离根最远的结点x，使得x同时为结点u、v的祖先。祖先：从该节点到达根节点的路径上的节点均是该节点的祖先。(自己是自己的祖先),看两种情况：,2,6,4,3,2,1,5,7,8,5,6,4,3,1,情况一：,情况二：,LCA(2,6)=2,LCA(6,8)=3,LCATarjan,建树，读入并保存所有询问。对以T为根节点的树进行后根遍历。遍历的同时，将已访问的节点按原先的父子顺序建立并查集。对于每一次询问Q(a,b)，若a已被访问，则LCA(a,b)为当前并查集的根节点，保存信息。,Code,LCA(u)Make-Set(u)ances

12、torFind-Set(u)=u对于u的每一个孩子vLCA(v)Union(u)ancestorFind-Set(u)=ucheckedu=true对于每个(u,v)属于Pifcheckedv=truethen回答u和v的最近公共祖先为ancestorFind-Set(v),LCATarjan算法总结,解决LCA问题的Tarjan算法利用并查集在一次DFS（深度优先遍历）中完成所有询问。它是时间复杂度为O(Na(N)+Q)，空间复杂度为O(N)的离线算法。,LCA问题的应用：,Howfaraway？(HDOJ2586),求在一颗无向树中，任意两点间的距离。,Floyd：TimeLimitExceeded,LCA：Accepted,distance(a,b)=disa+disb-2*dislca(a,b),区间最优值RMQ,把待求区间l,r分为两段长为len的区间左边一段为l,l+len-1,右边一段为r-len+1,rlen必须使得两段区间覆盖待求区间设所求数组为w那么