清北学堂讲义06朱全民并查集

1、并查集Yali 朱全民分离集合在有的问题中，需要对不相交的集合(disjoint set)进行这样两种操作：检索某元素属于哪个集合合并两个集合能够维护这两个操作的数据结构，我们称之为并查集。并查集的森林实现一般来说我们用森林的结构实现并查集在森林中，每棵树代表一个集合。用树根来表示这个集合。合并操作：两个集合S1、S2合并，将其中的一个树根作为另一个树根的子树即可。查找操作：对于一个元素u的查找，顺着u往上找，直到线索到根节点，也就确定了u所在的集合。两个优化启发式合并： 在合并集合S1、S2的时候，我们让较小的树成为较大的树的子树。这里可以是深度、节点个数等启发函数来比较树的大小。路径压缩：

2、 我们在查找完u至根节点的路径之后，一般将这条路径上的所有节点的父节点都设为根节点，这样可以大大减少之后的查找次数。并查集的时间复杂度可以证明，经过启发式合并和路径压缩之后的并查集，执行m次查找的复杂度为O(m(m)其中(m)是Ackermann函数的某个反函数，你可以近似的认为它是小于5的。所以并查集的单次查找操作的时间复杂度也几乎是常数级的。例一 银河英雄传说(NOI2002) 宇宙历七九九年，银河系的两大军事集团在巴米利恩星域爆发战争。泰山压顶集团派宇宙舰队司令莱因哈特率领十万余艘战舰出征，气吞山河集团点名将杨威利组织麾下三万艘战舰迎敌。 杨威利擅长排兵布阵，巧妙运用各种战术屡次以少胜多

3、，难免恣生骄气。在这次决战中，他将巴米利恩星域战场划分成30000列，每列依次编号为1, 2, , 30000。之后，他把自己的战舰也依次编号为1, 2, , 30000，让第i号战舰处于第i列(i = 1, 2, , 30000)，形成“一字长蛇阵”，诱敌深入。这是初始阵形。当进犯之敌到达时，杨威利会多次发布合并指令，将大部分战舰集中在某几列上，实施密集攻击。合并指令为M i j，含义为让第i号战舰所在的整个战舰队列，作为一个整体（头在前尾在后）接至第j号战舰所在的战舰队列的尾部。显然战舰队列是由处于同一列的一个或多个战舰组成的。合并指令的执行结果会使队列增大。例一 银河英雄传说(NOI20

4、02) 然而，老谋深算的莱因哈特早已在战略上取得了主动。在交战中，他可以通过庞大的情报网络随时监听杨威利的舰队调动指令。 在杨威利发布指令调动舰队的同时，莱因哈特为了及时了解当前杨威利的战舰分布情况，也会发出一些询问指令：C i j。该指令意思是，询问电脑，杨威利的第i号战舰与第j号战舰当前是否在同一列中，如果在同一列中，那么它们之间布置有多少战舰。 作为一个资深的高级程序设计员，你被要求编写程序分析杨威利的指令，以及回答莱因哈特的询问。例一 银河英雄传说(NOI2002)观察这个题目，开始时每条战舰作为独立的队列。随着M命令的发布，分离的队列不断合并。而且途中我们需要知道一些元素（战舰）的信

5、息这些性质启发我们应用并查集的数据结构解决例一 银河英雄传说(NOI2002)由于我们要得到的信息除了某条战舰在哪个队列，还要知道它在该队列中的位置。因此需要对并查集进行扩充。定义：ai：战舰i暂时标记为属于以战舰ai为首的队列，称战舰ai为战舰i的父节点bi：战舰i到战舰ai（包括战舰ai）之间的战舰数量，称bi为战舰i到战舰ai的深度。ci：战舰i所属队列后方（包括战舰i本身）的战舰数量（注意：此变量只有当ai=i时才有意义），称ci为队列长度。例一 银河英雄传说(NOI2002)初始时：ai=i，bi=0，ci=1对于每个M i j命令，需要进行如下操作：对战舰i,j进行查找和路径压缩设

6、ai=r1,aj=r2且r1r2，则：ar1=r2，br1=cr2，cr2=cr1+cr2对于每个C i j命令，需要进行如下操作：对战舰i,j进行查找和路径压缩判断是否有ai=aj，如是则表示他们是同一队列，输出|bi-bj|-1；如果不是则输出-1例一 银河英雄传说(NOI2002)关于战舰i的路径压缩的步骤：从i出发寻找根root，并累计从i到根root的深度，得到bi再次遍历从i出发到root的路径。对于途中的每一个节点k（假设在修改k之前ak=a1,bk=b1)，则我们根据已经修改过的战舰k的a、b值对战舰a1的a、b值进行修改，即： aa1=root，ba1=bk-b1例一 银河英

7、雄传说(NOI2002)结合并查集的时间复杂度的理论，可以得到该算法的时间复杂度大约为O(K)本题我们对并查集模型本身进行巧妙的修改，得到了高效地解决办法。下面我们来看一个对问题的形式进行修改，使得它能够应用并查集的例子。例二 可爱的猴子(POI2003)树上挂着n只可爱的猴子，编号为1,n (2=n=200 000)。猴子1的尾巴挂在树上，每只猴子有两只手，每只手可以最多抓住一只猴子的尾巴。所有的猴子都是悬空的，因此如果一旦脱离了树，猴子会立刻掉到地上。第0,1,m(1=m=400000)秒钟每一秒都有某个猴子把它的某只手松开，因此常常有猴子掉到地上。现在请你根据这些信息，计算出每个猴子掉在

8、地上的时间。例二 可爱的猴子(POI2003)如果把连在一起的猴子看成一个集合，每次松手就是断开了集合之间的某些联系或者直接将一个集合分离成两个。我们要求的是每只猴子第一次脱离猴子1所在集合的时间。“分查集”？例二 可爱的猴子(POI2003)我们不妨反过来想，如果时间从第m秒开始倒流，则出现的情形就是不断有某只猴子的手抓住另一只猴子。则我们要求的就转化成了：每只猴子最开始在什么时候合并到猴子1所在的集合。这样就可以应用并查集了。例二 可爱的猴子(POI2003)设在第t秒钟，猴子i抓住（实际上是放开）了猴子j，那么此时就将i所在的集合与j所在的集合合并。如果需要合并，并且原先猴子i与猴子 j在同一个集合，那么就将猴子j所在集合的所有猴子掉落的时刻都是t为了枚举某一个集合里的所