《集训队讲座第十讲并查集的深化与扩展》由会员分享，可在线阅读，更多相关《集训队讲座第十讲并查集的深化与扩展（49页珍藏版）》请在金锄头文库上搜索。
1、集训队讲座集训队讲座-第十第十讲讲并查集的深化与扩展并查集的深化与扩展(Merge_Find_Set)Index1：并查集的概念。2：并查集的优化。3：并查集的扩展。4：并查集的应用：LCA Tarjan算法。5：区间最优值 RMQ 算法。概念与实现方式n概念概念：并查集不相交集合n每棵树一个集合,根为集合标识。n树的形态并不重要,重要的是有哪些节点n实现方式实现方式：n一维数组的“森林表示法”。n几个定义：祖先，父亲，子孙生活中的集合并查集的基本操作nMakeSet(x)：建立一个新集合x。x应该不在现有的任何一个集合中出现。nFind(S,x)：返回x所在集合的代表元素。nMerge(x,
2、y)：把x所在的集合和y所在的集合合并。不可忽视的弊端：无法高效的找寻儿子节点！无法高效的找寻儿子节点！并查集的优化n1：启发式并查集：n让深度较小的树成为深度较大的树的子树n2：路径压缩：n找到最久远的祖先时“顺便”把它的子孙直接连接到它上面启发式并查集1564维护一个dep数组记入元素代表的有向树的深度。每次合并操作将深度较小的集合合并到深度较大的集合中，并维护dep数组。237Dep1=2dep4=3启发式并查集1.boolMerge(intx,inty)2.x=find(x);3.y=find(y);4.if(x!=y)returnfalse;5.if(depxdepy)treey=x
3、;7.elsetreex=y,depy+;8.returntrue;9.路径压缩4961111081220211661218211611209104路径压缩的实现n递归式：1.intfind(intx)2.if(treex=-1)3.returnx;4.returntreex=find(treex);5.路径压缩的实现n非递归式：1.intfind(intx)2.r=x;3.while(treer!=-1)r=treer;4.i=x;5.while(i!=r)6.j=treei;treei=r;i=j;7.8.returnr;复杂度分析并查集进行n次查找的时间复杂度是:O(n*)！可以看做一个
4、小于5的常数K，所以进行一次并查集操作的时间复杂度为：O(K)!小试身手Supermarket(POJ1456)SupermarketInput:4502101202301Output:80思考一下解题小技巧！n1：看数据量，估测复杂度。n2：思考如何将实际题目与集合的概念联系起来。n3：如何建立模型，如何用 查找 合并 两大操作来完成题目所要实现的动态过程。解题的关键贪心思想！思考！该如何贪心？证明贪心思想的正确性！给出一种贪心方法n1：按价值从大到小排序。n2：对于每个商品，选择它目前为止能到达的最靠后的时间卖出。复杂度估计复杂度估计并查集解决！并查集解决！并查集解决01234567891
5、0 11 12 13 14黄色：已被占用；绿色：等待被占用；粉红：已经无法使用，跳出。节点的删除Junk-MailFilter最初每个元素都属于自己的集合MXY：合并X所在的集合和Y所在的集合SX：把X从它所在的集合里删除请问：最后的集合个数？方法：“找替身”2653415*4*3*2*1*6*黄色：真身黄色：真身绿色：替身绿色：替身实现方法123456789 处理一个n=5的可删除节点的并查集：真身真身替身替身等待做替身等待做替身求元素的个数VirtualFriendsInput：13FredBarneyBarneyBettyBettyWilmaOutput：234添加变量：n记变量cnti
6、表示以i为代表元素的集合的元素个数。n注意：该变量只对祖先节点有效，非祖先节点的cnt没有实际意义。如何更新cnt数组n初始化每个集合的元素个数为1。n当进行元素查找时，不做任何处理。n当进行集合合并时，将被合并的集合的元素个数叠加到合并后的大集合中。注意：区分此处cnt数组 和 启发式并查集中dep数组。合并过程17103241196581110897164325cnt1=5cnt6=6cnt6=11红色节点的cnt数组有效！再次深入：带权值的并查集食物链食物链动物王国中有三类动物A,B,C，这三类动物的食物链构成了有趣的环形。A吃B，B吃C，C吃A。现有N个动物。每个动物都是A,B,C中的
7、一种，但是我们并不知道它到底是哪一种。有人用两种说法对这N个动物所构成的食物链关系进行描述：第一种说法是1XY，表示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），输出假话的总数。试着来分析一下n1：如何来构造集合？n2：如何来判断是否冲突？n3：如何来记
8、入信息？困惑：表示元素之间的关系 并且 高效的查找记入树中每个孩子节点到记入树中每个孩子节点到记入树中每个孩子节点到记入树中每个孩子节点到父亲节点父亲节点父亲节点父亲节点的距离！的距离！的距离！的距离！定义height变量nheightA%3=0：nA与根节点是同类。nheightA%3=1：n根吃A。nheightA%3=2：nA吃根。用TreeB=A来表示：A吃B保存有效信息Input:100711011212223233113231155Output:31 X Y: 表示X和Y是同类。2 X Y: 表示X吃Y。123height1=0height2=1height3=1123height
9、1=0height2=1height3=2判断信息的正确性n当输入为1XY时？n当输入为2XY时？抓住本质！不同的输入，相同的处理！回想&反思：n1：为什么height是记录到父亲节点的距离？n2：并查集是如何在路径压缩后保持它的正确性，操作上的注意点！温故知新structMFsetintfather;/父亲节点intheight;/到父亲的距离intdep;/有向树的深度intcnt;/集合的元素个数intFind(intx)boolMerge(intx,inty)voidDelete(intx)treeMAXN;综合练习1：银河英雄传说银河英雄传说宇宙历七九九年，银河系的两大军事集团在巴米
10、利恩星域爆发战争。泰山压顶集团派宇宙舰队司令莱因哈特率领十万余艘战舰出征，气吞山河集团点名将杨威利组织麾下三万艘战舰迎敌。M i j：让第i号战舰所在的整个战舰队列，作为一个整体（头在前尾在后）接至第j号战舰所在的战舰队列的尾部。 C i j：询问电脑，杨威利的第i号战舰与第j号战舰当前是否在同一列中，如果在同一列中，那么它们之间布置有多少战舰。 逐步分析各个击破n集合的概念体现在哪里？nMij的处理方法？nCij的处理方法？n需要用到哪些并查集的特征变量？n合并时，这些变量该怎样更新？定义变量：nfatheri:排在战舰i前面且相邻的战舰。nheighti:战舰i到战舰fatheri之间的战
11、舰的数量。ncnti:战舰i所属队列的后方(包括i)的战舰数量。(该数组只对首战舰有效！)综合练习2：Exclusive-OR另类的并查集ConnectionsinGalaxyWar方法：把所有数据都保存下来，然后倒着处理。对于提出的问题：及时回答，保存答案。对于删去的树枝：做并查集的合并处理。运用：最近公共祖先LCAn概念：LeastCommonAncestors对于有根树T的两个结点u、v，最近公共祖先LCA(T,u,v)：询问一个距离根最远的结点x，使得x同时为结点u、v的祖先。n祖先：从该节点到达根节点的路径上的节点均是该节点的祖先。(自己是自己的祖先)看两种情况：2643215785
12、6431情况一：情况二：LCA(2,6)=2LCA(6,8)=3LCATarjan1.建树，读入并保存所有询问。2.对以T为根节点的树进行后根遍历。3.遍历的同时，将已访问的节点按原先的父子顺序建立并查集。4.对于每一次询问Q(a,b)，若a已被访问，则LCA(a,b)为当前并查集的根节点，保存信息。CodeLCA(u)Make-Set(u)ancestorFind-Set(u)=u对于u的每一个孩子vLCA(v)Union(u)ancestorFind-Set(u)=ucheckedu=true对于每个(u,v)属于Pifcheckedv=truethen回答u和v的最近公共祖先为ances
13、torFind-Set(v)LCATarjan算法总结n解决LCA问题的Tarjan算法利用并查集在一次DFS（深度优先遍历）中完成所有询问。它是时间复杂度为O(Na(N)+Q)，空间复杂度为O(N)的离线算法。LCA问题的应用：Howfaraway？(HDOJ2586)求在一颗无向树中，任意两点间的距离。Floyd：TimeLimitExceededLCA：Accepteddistance(a,b)=disa+disb-2*dislca(a,b)区间最优值RMQ把待求区间l,r分为两段长为len的区间左边一段为l,l+len-1,右边一段为r-len+1,rlen必须使得两段区间覆盖待求区间设所求数组为w那么,所求最小值就是两个区间的最小值间的最小值即min(minwi,l=i=l+len-1,minwj,r-len+1=j=r)RMQ模板检测题BalancedLineup(PKU3264)已知n个数，求区间a,b间的最大值减去最小值的值。Interviewe(HDOJ3486)总结一下并查集题目的特点：n数据规模？n题目特征？n输入输出？Welcome to HDOJThank You
