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

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

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

3、turn false;if (depx depy) treey = x;else treex = y, depy +;return true;第八页，共五十页。路径压缩4961111081220211661218211611209104第九页，共五十页。路径压缩的实现递归式：int find(int x) if(treex = -1) return x;return treex = find(treex);第十页，共五十页。路径压缩的实现非递归式：int find (int x) r = x; while (treer != -1) r = treer; i = x; while (i !=

4、r) j = treei; treei = r; i = j; return r;第十一页，共五十页。复杂度分析并查集进行n次查找的时间复杂度是:O (n * ) ！ 可以看做一个小于5的常数K，所以进行一次并查集操作的时间复杂度为：O(K) !第十二页，共五十页。小试身手Supermarket (POJ1456)第十三页，共五十页。SupermarketInput:4 50 2 10 1 20 2 30 1Output:80思考一下第十四页，共五十页。解题小技巧！1：看数据量，估测复杂度。2：思考如何将实际题目与集合的概念联系起来。3：如何建立模型，如何用 查找 合并 两大操作来完成题目所要

5、实现的动态过程。第十五页，共五十页。解题的关键贪心思想！思考！该如何贪心？证明贪心思想的正确性！第十六页，共五十页。给出一种贪心方法1：按价值从大到小排序。2：对于每个商品，选择它目前为止能到达的最靠后的时间卖出。复杂度估计并查集解决！第十七页，共五十页。并查集解决01234567891011121314黄色：已被占用；绿色：等待被占用；粉红：已经无法使用，跳出。第十八页，共五十页。节点的删除 Junk-Mail Filter最初每个元素都属于自己的集合M X Y ：合并X所在的集合和Y所在的集合S X ：把X从它所在的集合里删除请问：最后的集合个数？第十九页，共五十页。方法：“找替身”265

6、3415*4*3*2*1*6*黄色：真身绿色：替身第二十页，共五十页。实现方法123456789处理一个 n = 5 的可删除节点的并查集：真身替身等待做替身第二十一页，共五十页。求元素的个数 Virtual FriendsInput：13Fred BarneyBarney BettyBetty WilmaOutput：2 3 4第二十二页，共五十页。添加变量：记变量cnti表示以i为代表元素的集合的元素个数。注意：该变量只对祖先节点有效，非祖先节点的cnt没有实际意义。第二十三页，共五十页。如何更新cnt数组初始化每个集合的元素个数为1。当进行元素查找时，不做任何处理。当进行集合合并时，将被

7、合并的集合的元素个数叠加到合并后的大集合中。注意：区分此处cnt数组 和 启发式并查集中dep数组。第二十四页，共五十页。合并过程17103241196581110897164325cnt1 = 5cnt6 = 6cnt6 = 11红色节点的cnt数组有效！第二十五页，共五十页。再次深入：带权值的并查集食物链第二十六页，共五十页。食物链动物王国中有三类动物A,B,C，这三类动物的食物链构成了有趣的环形。A吃B， B吃C，C吃A。 现有N个动物。每个动物都是A,B,C中的一种，但是我们并不知道它到底是哪一种。 有人用两种说法对这N个动物所构成的食物链关系进行描述： 第一种说法是1 X Y，表示X

8、和Y是同类。 第二种说法是2 X Y，表示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：如何来记入信息？困惑：表示元素之间的关系 并且 高效的查找记入树中每

9、个孩子节点到父亲节点的距离！第二十八页，共五十页。定义height变量heightA % 3 = 0：A与根节点是同类。heightA % 3 = 1：根吃A。heightA % 3 = 2：A吃根。用 TreeB = A来表示：A吃B第二十九页，共五十页。保存有效信息Input:100 71 101 1 2 1 22 2 3 2 3 3 1 1 3 2 3 1 1 5 5Output:31 X Y: 表示X和Y是同类。2 X Y: 表示X吃Y。123height1 = 0height2 = 1height3 = 1123height1 = 0height2 = 1height3 = 2第三十

10、页，共五十页。判断信息的正确性当输入为1 X Y时？当输入为2 X Y时？抓住本质！不同的输入，相同的处理！第三十一页，共五十页。回想 & 反思：1：为什么height是记录到父亲节点的距离？2：并查集是如何在路径压缩后保持它的正确性，操作上的注意点！第三十二页，共五十页。温故知新struct MFset int father; /父亲节点 int height; /到父亲的距离 int dep; /有向树的深度 int cnt; /集合的元素个数 int Find(int x) bool Merge(int x,int y) void Delete(int x)treeMAXN;第三十三页，

11、共五十页。综合练习1：银河英雄传说第三十四页，共五十页。银河英雄传说宇宙历七九九年，银河系的两大军事集团在巴米利恩星域爆发战争。泰山压顶集团派宇宙舰队司令莱因哈特率领十万余艘战舰出征，气吞山河集团点名将杨威利组织麾下三万艘战舰迎敌。 M i j：让第i号战舰所在的整个战舰队列，作为一个整体（头在前尾在后）接至第j号战舰所在的战舰队列的尾部。 C i j：询问电脑，杨威利的第i号战舰与第j号战舰当前是否在同一列中，如果在同一列中，那么它们之间布置有多少战舰。 第三十五页，共五十页。逐步分析 各个击破集合的概念体现在哪里？M i j 的处理方法？C i j 的处理方法？需要用到哪些并查集的特征变量

12、？合并时，这些变量该怎样更新？第三十六页，共五十页。定义变量：fatheri:排在战舰i前面且相邻的战舰。heighti:战舰i到战舰fatheri之间的战舰的数量。cnti:战舰i所属队列的后方(包括i)的战舰数量。(该数组只对首战舰有效！)第三十七页，共五十页。综合练习2：Exclusive-OR第三十八页，共五十页。另类的并查集Connections in Galaxy War方法：把所有数据都保存下来，然后倒着处理。对于提出的问题：及时回答，保存答案。对于删去的树枝：做并查集的合并处理。第三十九页，共五十页。运用：最近公共祖先LCA概念：Least Common Ancestors 对

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

14、LCA(u) Make-Set(u) ancestorFind-Set(u)=u 对于u的每一个孩子v LCA(v) Union(u) ancestorFind-Set(u)=u checkedu=true 对于每个(u,v)属于P if checkedv=true then 回答u和v的最近公共祖先为 ancestorFind-Set(v) 第四十三页，共五十页。LCA Tarjan算法 总结解决LCA问题的Tarjan算法利用并查集在一次DFS（深度优先遍历）中完成所有询问。它是时间复杂度为O(Na(N) + Q)，空间复杂度为 O(N)的离线算法。第四十四页，共五十页。LCA问题的应用：

15、How far away ？(HDOJ2586)求在一颗无向树中，任意两点间的距离。Floyd：Time Limit ExceededLCA：Accepteddistance(a,b) = disa + disb - 2*dislca(a,b)第四十五页，共五十页。区间最优值 RMQ把待求区间l,r分为两段长为len的区间 左边一段为l,l+len-1,右边一段为r-len+1,r len必须使得两段区间覆盖待求区间设所求数组为w那么,所求最小值就是两个区间的最小值间的最小值即min(minwi,l=i=l+len-1,minwj, r-len+1=j=r)第四十六页，共五十页。RMQ 模板检测题Balanced Lineup(PKU3264)已知n个数，求区间a,b间的最大值减去最小值的值。Interviewe(HDOJ3486)第四十七页，共五十页。总结一下并查集题目的特点：数据规模？题目特征？输入输出？第四十八页，共五十页。Wel