集训队讲座第十讲并查集的深化与扩展教学文稿

集训队讲座第十讲并查集的深化与扩展概念与实现方式概念：并查集——不相交集合每棵树一个集合,根为集合标识。树的形态并不重要,重要的是有哪些节点实现方式：一维数组的“森林表示法”。几个定义：祖先，父亲，子孙~生活中的集合~并查集的基本操作MakeSet(x)：建立一个新集合x。x应该不在现有的任何一个集合中出现。Find(S,x)：返回x所在集合的代表元素。Merge(x,y)：把x所在的集合和y所在的集合合并。不可忽视的弊端：无法高效的找寻儿子节点！！！并查集的优化1：启发式并查集：让深度较小的树成为深度较大的树的子树~2：路径压缩：找到最久远的祖先时“顺便”把它的子孙直接连接到它上面~启发式并查集1564维护一个dep[]数组记入元素代表的有向树的深度。每次合并操作将深度较小的集合合并到深度较大的集合中，并维护dep数组。237Dep[1]==2dep[4]==3启发式并查集boolMerge(intx,inty){ x=find(x); y=find(y);

if(x!=y)returnfalse;

if(dep[x]<dep[y])tree[x]=y;

elseif(dep[x]>dep[y])tree[y]=x;

elsetree[x]=y,dep[y]++;

returntrue;}路径压缩4961111081220211661218211611209104路径压缩的实现递归式：intfind(intx){

if(tree[x]==-1)

returnx;

returntree[x]=find(tree[x]);}路径压缩的实现非递归式：int

find(intx){r=x;

while(tree[r]!=-1)r=tree[r];i=x;

while(i!=r){j=tree[i];tree[i]=r;i=j;}

returnr;

}复杂度分析~并查集进行n次查找的时间复杂度是:O(n*)！！！可以看做一个小于5的常数K，所以进行一次并查集操作的时间复杂度为：O(K)!小试身手~Supermarket(POJ1456)SupermarketInput:4502101202301Output:80思考一下~解题小技巧！1：看数据量，估测复杂度。2：思考如何将实际题目与集合的概念联系起来。3：如何建立模型，如何用查找

合并两大操作来完成题目所要实现的动态过程。解题的关键——贪心思想！思考！该如何贪心？证明贪心思想的正确性！给出一种贪心方法1：按价值从大到小排序。2：对于每个商品，选择它目前为止能到达的最靠后的时间卖出。复杂度估计~并查集解决！并查集解决~01234567891011121314黄色：已被占用；绿色：等待被占用；粉红：已经无法使用，跳出。节点的删除Junk-MailFilter最初每个元素都属于自己的集合MXY：合并X所在的集合和Y所在的集合SX：把X从它所在的集合里删除请问：最后的集合个数？方法：“找替身”~2653415*4*3*2*1*6*黄色：真身绿色：替身实现方法~123456789…处理一个n==5的可删除节点的并查集：真身替身等待做替身求元素的个数VirtualFriendsInput：13FredBarneyBarneyBettyBettyWilmaOutput：234添加变量：记变量cnt[i]表示以i为代表元素的集合的元素个数。注意：该变量只对祖先节点有效，非祖先节点的cnt没有实际意义。如何更新cnt数组初始化每个集合的元素个数为1。当进行元素查找时，不做任何处理。当进行集合合并时，将被合并的集合的元素个数叠加到合并后的大集合中。注意：区分此处cnt[]数组和启发式并查集中dep[]数组。合并过程~17103241196581110897164325cnt[1]==5cnt[6]==6cnt[6]==11红色节点的cnt数组有效！！！再次深入：带权值的并查集食物链食物链动物王国中有三类动物A,B,C，这三类动物的食物链构成了有趣的环形。A吃B，B吃C，C吃A。

现有N个动物。每个动物都是A,B,C中的一种，但是我们并不知道它到底是哪一种。

有人用两种说法对这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），输出假话的总数。试着来分析一下~1：如何来构造集合？2：如何来判断是否冲突？3：如何来记入信息？困惑：表示元素之间的关系并且高效的查找记入树中每个孩子节点到父亲节点的距离！！！定义height变量height[A]%3==0：A与根节点是同类。height[A]%3==1：根吃A。height[A]%3==2：A吃根。用Tree[B]=A来表示：A吃B保存有效信息Input:100711011212223233113231155Output:31XY:表示X和Y是同类。2XY:表示X吃Y。123height[1]=0height[2]=1height[3]=1123height[1]=0height[2]=1height[3]=2判断信息的正确性当输入为1XY时？当输入为2XY时？抓住本质！！不同的输入，相同的处理！回想&反思：1：为什么height[]是记录到父亲节点的距离？2：并查集是如何在路径压缩后保持它的正确性，操作上的注意点！温故知新structMFset{

intfather;

//父亲节点

intheight;

//到父亲的距离

intdep;

//有向树的深度

intcnt;

//集合的元素个数

intFind(intx){}

boolMerge(intx,inty){}

voidDelete(intx){}}tree[MAXN];综合练习1：银河英雄传说~银河英雄传说~宇宙历七九九年，银河系的两大军事集团在巴米利恩星域爆发战争。泰山压顶集团派宇宙舰队司令莱因哈特率领十万余艘战舰出征，气吞山河集团点名将杨威利组织麾下三万艘战舰迎敌。

Mij：让第i号战舰所在的整个战舰队列，作为一个整体（头在前尾在后）接至第j号战舰所在的战舰队列的尾部。Cij：询问电脑，杨威利的第i号战舰与第j号战舰当前是否在同一列中，如果在同一列中，那么它们之间布置有多少战舰。逐步分析各个击破集合的概念体现在哪里？Mij的处理方法？Cij的处理方法？需要用到哪些并查集的特征变量？合并时，这些变量该怎样更新？定义变量：father[i]:排在战舰i前面且相邻的战舰。height[i]:战舰i到战舰father[i]之间的战舰的数量。cnt[i]:战舰i所属队列的后方(包括i)的战舰数量。(该数组只对首战舰有效！)综合练习2：Exclusive-OR另类的并查集ConnectionsinGalaxyWar方法：把所有数据都保存下来，然后倒着处理。对于提出的问题：及时回答，保存答案。对于删去的树枝：做并查集的合并处理。运用：最近公共祖先LCA概念：LeastCommonAncestors——对于有根树T的两个结点u、v，最近公共祖先LCA(T,u,v)：询问一个距离根最远的结点x，使得x同时为结点u、v的祖先。祖先：从该节点到达根节点的路径上的节点均是该节点的祖先。(自己是自己的祖先)

看两种情况：26432157856431情况一：情况二：LCA(2,6)=2LCA(6,8)=3LCATarjan建树，读入并保存所有询问。对以T为根节点的树进行后根遍历。遍历的同时，将已访问的节点按原先的父子顺序建立并查集。对于每一次询问Q(a,b)，若a已被访问，则LCA(a,b)为当前并查集的根节点，保存信息。Code~LCA(u)

{

Make-Set(u)

ancestor[Find-Set(u)]=u

对于u的每一个孩子v

{

LCA(v)

Union(u)

ancestor[Find-Set(u)]=u

}

checked[u]=true

对于每个(u,v)属于P

{

ifchecked[v]=true

then

回答u和v的最近公共祖先为ancestor[Find-Set(v)]

}

}LCATarjan算法总结解决LCA问题的Tarjan算法利用并查集在一次DFS（深度优先遍历）中完成所有询问。它是时间复杂度为O(Na(N)+Q)，空间复杂度为O(N)的离线算法。LCA问题的应用：Howfaraway？(HDOJ2586)求在一颗无向树中，任意两点间的距离。Floyd：TimeLimitExceededLCA：Accepteddistance(a,b)=dis[a]+dis[b]-2*dis[lca(a,b)]区间最优值RMQ把待求区间[l,r]分为两段长为len的区间左边一段为[l,l+len-1],右边一段为[r-len+1,r]len必须使得两段区间覆盖待求区间设所求数组为w那么,所求最小值就是两个区间的