并查集(最终版).ppt

1、并查集,JSOI2015冬令营,并查集基本概念 并查集基本操作 并查集应用举例,问题描述：或许你并不知道，你的某个朋友是你的亲戚。他可能是你的曾祖父的外公的女婿的外甥女的表姐的孙子！ 如果能得到完整的家谱，判断两个人是否亲戚应该是可行的，但如果两个人的最近公共祖先与他们相隔好几代，使得家谱十分庞大，那么检验亲戚关系实非人力所能及。在这种情况下，最好的帮手就是计算机。为了将问题简化，你将得到一些亲戚关系的信息，如Marry和Tom是亲戚，Tom和Ben是亲戚，等等。从这些信息中，你可以推出Marry和Ben是亲戚。,例1：亲戚,输入: 由两部分组成： 第一部分以N，M开始。N为问题涉及的人的个数

2、。这些人的编号为1,2,3, N。下面有M行，每行有两个数ai, bi，表示已知ai和bi是亲戚。 第二部分以Q开始。以下Q行有Q个询问，每行为ci, di，表示询问ci和di是否为亲戚。 输出：对于每个询问ci, di，输出一行：若ci和di为亲戚，则输出“Yes”，否则输出“No”。,请写一个程序，对于我们的关于亲戚关系的提问，以最快的速度给出答案。,输入样例（relation.in）： 10 7 2 4 5 7 1 3 8 9 1 2 5 6 2 3 3 3 4 7 10 8 9,输出样例（relation.out）： Yes No Yes,问题规模1： 1 N 255 1 M 1 00

3、0 000 1 Q 1 000 000,各抒己见,思路点拔,题意分析 算法及数据结构设计 时间、空间复杂度估计及实践细节讨论 优化思路讨论,输入关系 分离集合 初始状态 12345678910 (2,4) 12,435678910 (5,7) 12,435,768910 (1,3) 1,32,45,768910 (8,9) 1,32,45,768,910 (1,2) 1,2,3,45,768,910 (5,6) 1,2,3,45,6,78,910 (2,3) 1,2,3,45,6,78,910,实时判断,集 合,定义及运算：var s:set of 1.100; 集合与集合：交A*B、并A+B

4、、差A-B，结果还是集合； 关系运算 相等=、不相等、包含于=，结果为boolean； 元素与集合：x in s，结果为boolean；,集合的优缺点：容易理解，运算简单； 数据量小、调试不方便；,问题规模2： 1 N 20000 1 M 1 000 000 1 Q 1 000 000,并查集,并查集（union-find set）是一种用于分离集合操作的抽象数据类型。它所处理的是“集合”之间的关系，即动态地维护和处理集合元素之间复杂的关系，当给出两个元素的一个无序对(a,b)时，需要快速“合并”a和b分别所在的集合，这其间需要反复“查找”某个元素所在的集合。“并”、“查”和“集”三字由此而来

5、。在这种数据类型中，n个不同的元素被分为若干组。每组是一个集合，这种集合叫做分离集合（disjoint set）。并查集支持查找一个元素所属的集合以及两个元素各自所属的集合的合并。,如何用已有的数据类型或数据结构去构造？,并查集本身不具有结构，必须借助一定的数据结构以得到支持和实现。数据结构的选择是一个重要的环节，选择不同的数据结构可能会在查找和合并的操作效率上有很大的差别，但操作实现都比较简单高效。并查集的数据结构实现方法很多，一般用的比较多的是，数组实现、链表实现和树实现。,并查集,并查集的数据结构记录了一组分离的动态集合S，S=S1,S2,Sk，每个集合通过一个“代表”加以识别，代表即该

6、集合中的某个元素（成员），哪一个成员被选做代表是无所谓的，重要的是：如果求某一动态集合的代表两次，且在两次请求间不修改此集合，则两次得到的答案应该是相同的。,动态集合中的每一元素是由一个对象来表示的，设x表示一个对象，并查集的实现需要支持如下操作：,并查集的基本操作, MAKE-SET（x） 建立一个新的集合，其仅有的成员（同时就是代表）是x。由于各集合是分离的，所以要求x没有在其它集合中出现过。 UNION（x,y） 将包含x和y的动态集合（例如Sx和Sy）合并为一个新的集合，假定在此操作前这两个集合是分离的。结果的集合代表是SxSy的某个成员。一般来说，在不同的实现中通常都以Sx或者Sy的

7、代表作为新集合的代表。此后，由新的集合S代替了原来的Sx和Sy。 FIND-SET（x） 返回一个包含x的集合的代表。,并查集的数组实现,输入样例： 10 7 2 4 5 7 1 3 8 9 1 2 5 6 2 3 3 3 4 7 10 8 9,UNION（x,y）过程演示：,S,1 2 3 4 5 6 7 8 9 10,S,1 2 3 4 5 6 7 8 9 10,用数组si记录元素i所属集合的编号。 MAKE-SET（x）：初始化只要si：=i； FIND-SET（x）：查找元素所属的集合时，只需读出si，时间复杂度为O(1)。 UNION（x,y）：合并两元素各自所属的集合时，需要将数组

8、中属于其中一个集合的元素所对应的数组元素值全部改为另一个集合的编号值，时间复杂度为O(n)。 实现简单，实际使用较多。但是合并的代价太大，在最坏情况下，所有集合合并成一个集合的总代价会达到O(n2)。,每个集合对应一个链表，它有一个表头，每一个元素有一个指针指向表头，表明了它所属的类，另有一个指针指向它的下一个元素,同时为了方便实现，再设一个指针last表示链表中的最后一个元素（表尾）。 当然，由于处理的对象一般都是连续整数，所以，可以选择静态数组（通过下标）来模拟实现，如： type node = record head,next,last:integer; end; var S : arr

9、ay1.maxn of node;,并查集的链表实现,MAKE-SET(x)：Sx.head = x;Sx.next = 0; FIND-SET(x)：return Sx.head; 两个过程的时间复杂度都为O(1)。 采用链表时，当有两个元素(x,y),若FIND-SET（x） FIND-SET（y），则两者对应不同的集合，需要将两个链表合并，做法是将一个表的表头直接接到另一个表的表尾，这一步操作看似很简单，但势必造成修改后需要把接上去的那个表的所有head值修改，这需要线性的赋值操作，其复杂度与选择接在尾部的链表长度成正比。,UNION(x,y)： 假设UNION(x,y)的参数是有序的，

10、即把y属于的集合合并到x的集合有两种实现方法：,（1）简单实现 不考虑任何因素，出现FIND-SET（x） FIND-SET（y）时，直接将y的表头接到x的表尾，同时将y中所在集合元素的head值设为FIND-SET(x)。同时x的表尾也应该设为原y表的表尾。 注意：last指针其实只要在表头结点中记录即可，因为每一次查到FIND-SET（x）都可以得到表头元素。而链表中其他元素重新记录last是无意义的。 我们总是把y接到x里去，那么如果y所在的集合非常大，每次赋值的代价就会非常高，考虑输入数据的特殊性，比如出现输入为： （2，1），（3，1），（4，1），（5，1），（6，1） ， ，(n

11、,1) 最坏情况下时间复杂度为O(n2)。,（2）快速实现 上述简单实现非常不理想，针对y可能比较大的这个问题，可以很快产生一个聪明的想法：不妨比较x和y所在集合的大小，从而作出选择，把较短的链表接在较长的尾部，这样效果是一样的，但耗费肯定不比原来差。这就是快速实现的思路。可以在node里多设一个域number，用来记录此条链表中成员的个数。显然number记录在表头元素中即可，将两表合并的时候，只要将表的number相加，因此维护起来是非常方便的。 这种快速实现的方法可以称为加权启发式合并，这里的权就是指所记录的number。,可以证明这种方法的效率。当有n个元素时，在UNION上的花费（即

12、重新赋值的次数）的上界是O(nlog2n)。因为：考虑一个固定的对象x，当x的代表指针（head）被更新时，x必是属于一个较小的集合，因此，x的代表指针第一次更新后，结果集合必然至少有2个元素，类似的，下一次更新后，x所在的集合至少有4个元素。继续下去，可以发现，x的代表指针最多被更新log2n次，因为当x所在集合元素已经等于n以后，不可能再发生UNION操作。所以，总共有n个元素时，操作的总次数不超过nlog2n次。这就保证了整个算法的复杂度是理想的。,并查集的链表实现是一种非常容易接受的算法，并且它的效率也是令人满意的。其实它的思路和数组完全一样，所以实际使用较少。,合并两个集合时的实现过

13、程如下： UNION(x,y) x = FIND-SET(x); y = FIND-SET(y); if x.numbery.number then UNION(x,y) else UNION(y,x); ,我们用有根树来表示集合，树中的每个节点包含集合的一个成员，每棵树表示一个集合。多个集合形成森林态，以每棵树的树根作为集合的代表，并且根结点的父结点指向其自身，树上的其他结点都用一个父指针表示它的附属关系。 注意：在同一棵树中的结点属于同一个集合，虽然它们在树中存在父子结点关系，但并不意味着它们之间存在从属关系。树的指针起的只是联系集合中元素的作用。 在并查集中，每个分离集合对应的一棵树，称

14、为分离集合树。整个并查集也就是一棵分离集合森林。,并查集的树实现,如下图表示了这种关系，其包含两个集合b,c,e,h,d,f,g分别以c和f作为代表。,这种树结构，也可以简单地用静态数组实现，设px表示x元素所指向的父亲。 MAKE-SET(x)：px=x; FIND-SET(x)：要从x开始，向上寻找它的父亲，直到找到根为止。 UNION（x,y）：只要使一棵树的根指向另一棵树的根，即成为一棵子树。,1查找一个元素所属的集合 在分离集合森林中，每一棵分离集合树对应一个集合。要查找某一元素所属的集合，就是要找这个元素对应的结点所在的分离集合树。,查找树的根结点的方法很简单，只需任取树中一结点（

15、不妨就取我们要查找的那个结点），沿父结点方向一直往树根走：初始时，取一个结点，走到它的父结点，然后以父结点为基点，走到父结点的父结点直至走到一个没有父结点的结点为止，这个结点就是树的根结点。如图，描述了查找一个结点的过程（黑色结点为当前查找结点）。,2两个元素各自所属的集合的合并 在分离集合森林中，分离集合是用分离集合树来表示的。要合并两个元素各自所属的集合，也就是合并两元素所对应的两个结点各自所在的分离集合树。,考虑到在分离集合森林中，只要结点属于同一棵树，即被视为在同一个集合中，而不管具体是如何相连的。那么，我们只需简单的将一棵分离集合树作为另一棵的子树，即可使两棵树合并为一棵。如图，描述

16、的是将两棵分离集合树D1和D2合并的过程（D1作为D2的根结点的一棵子树）。,3优化查找与合并算法 优化合并过程 如果两棵分离集合树A和B，深度分别为hA和hB，则若hAhB，应将 B树作为A树的子 树；否则，将A树 作为B树的子树。,优化查找过程 对于查找过程有两个方面的启发式方法都很有效，分别是按秩合并和路径压缩优化。 A按秩合并 进行UNION的时候，只要让具有较小秩的根指向具有较大秩的根。如果两根的秩相等，只要使其中一个根指向另一个，同时秩应当增加1。这十分类似于统计节点个数，但这里统计的是树的深度。,B路径压缩优化方法 在查找一个结点所在树的根结点的过程中，要经过一条从待查结点到根结

17、点的路径。我们不妨就让这些路径上的结点直接指向根结点，作为根结点的子结点。这样，这些路径上的结点仍在分离集合中，整棵树仍然满足分离集合树的要求，而路径上的结点的深度无疑降低了，这些点及其子树上的结点的查找复杂度大大降低。,如图，描述了在一棵分离集合树查找结点7的前后所呈现出的结构。,优化后的代码： MAKE-SET(x) px=x；rankx=0； UNION(x,y) x = FIND-SET(x)；y=FIND-SET(Y)； if rankx ranky then py=x else px=y； if rankx = ranky then ranky = ranky+1; FIND-SE

18、T(x) if xpx then px=FIND-SET(px)； return px； ,并查集的应用,简单模型基本应用 优化算法整合应用 创新模型综合应用,例2：可爱的猴子(POI2003),一棵树上有n 只猴子，他们从1到n编号。编号为1 的猴子用它的尾巴盘住了一个树枝，剩下的猴子要么被其他的猴子钩住要么就是自己用手钩住其他的猴子。每只猴子都可以用两只手去钩其他的猴子,每只手最多只能钩一只。从0时刻开始,每一秒都有一只猴子松开它的一只手。这也许会造成一些猴子掉落到地上,我们想要知道它们掉落地上的时间(猴子掉落的速度都非常的快,可以忽略掉落的时间)。,输入： 第一行包含两个整数n和 m,

19、1 = n = 200000, 1 = m = 400000。整数 n 代表猴子总数, 数 m 代表我们观察猴子的总时间。接下来 n 行描述初始的情形，第 (k + 1) 行 (1 = k = n) 有两个整数分别代表猴子k的左手和右手分别抓住了哪两只猴子，-1 代表它的那只手是空的。 接下来m行代表我们观察到的猴子的活动，第i行有两个整数(1 = i = m) 代表在第i 1时刻放开手的是哪只猴子和它放开的是哪只手(1 左, 2 右)。,输出： 输出n个整数每行一个代表每只猴子掉落到地 上的时间, 如果没有掉落, 输出-1. 输入样例： 3 2-1 33 -11 21 23 1 输出样例：

20、-111,例3：优化kruskal算法,Kruskal算法是一种贪心的求最小生成树的算法，具体操作是初始时所有的边都是未选边，图中只有点，每次选择一条权值最小的，连接在不同连通块的未选边，然后将这条未选边赋值为已选边。 经过n-1次操作之后，就求出了该图的最小生成树,例4：Ant Trip(HDU3018),Ant Country有N个小镇，小镇之间有M条路相连。Ant Tony和朋友们一起想游遍国内所有的小镇，对于每条路他们计划都要走一遍且只走一遍。然而，这对于一个团队来说，是一个几乎不可能完成的任务。因此，他们将分成若干个小组同时进行，每个小组可以从不同的小镇开始旅游，现在，tony 想知

21、道最少需要几个小组就可以完成这个旅游计划。,输入： 输入包含多组数据。每组数据之间用一些空行间隔，每组数据的第一行有两个整数N(1=N=100000),M(0=M=200000),表示Ant Country有N个小镇和M条路，接下来有M行，每行有两个整数a,b,(1=a,b=N)表示小镇 a和小镇b有一条路。没有两条相同的路，也没有一条路连接同一个小镇。 对于没有路连接的小镇，将直接忽略它。,输出：对于每组数据，输出完成旅游计划至少需要的小组数。 输入样例： 3 3 1 2 2 3 1 3 4 2 1 2 3 4,输出样例： 1 2,例5：银河英雄传说(NOI2002),宇宙历七九九年，银河系

22、的两大军事集团在巴米利恩星域爆发战争。泰山压顶集团派宇宙舰队司令莱因哈特率领十万余艘战舰出征，气吞山河集团点名将杨威利组织麾下三万艘战舰迎敌。 杨威利擅长排兵布阵，巧妙运用各种战术屡次以少胜多，难免恣生骄气。在这次决战中，他将巴米利恩星域战场划分成30000列，每列依次编号为1, 2, , 30000。之后，他把自己的战舰也依次编号为1, 2, , 30000，让第i号战舰处于第i列(i = 1, 2, , 30000)，形成“一字长蛇阵”，诱敌深入。这是初始阵形。当进犯之敌到达时，杨威利会多次发布合并指令，将大部分战舰集中在某几列上，实施密集攻击。合并指令为M i j，含义为让第i号战舰所在

23、的整个战舰队列，作为一个整体（头在前尾在后）接至第j号战舰所在的战舰队列的尾部。显然战舰队列是由处于同一列的一个或多个战舰组成的。合并指令的执行结果会使队列增大。,然而，老谋深算的莱因哈特早已在战略上取得了主动。在交战中，他可以通过庞大的情报网络随时监听杨威利的舰队调动指令。 在杨威利发布指令调动舰队的同时，莱因哈特为了及时了解当前杨威利的战舰分布情况，也会发出一些询问指令：C i j。该指令意思是，询问电脑，杨威利的第i号战舰与第j号战舰当前是否在同一列中，如果在同一列中，那么它们之间布置有多少战舰。 作为一个资深的高级程序设计员，你被要求编写程序分析杨威利的指令，以及回答莱因哈特的询问。,

24、输入: 输入文件galaxy.in的第一行有一个整数 T（1=T=500,000），表示总共有T条指令。以下有T行，每行有一条指令。指令有两种格式： M i j ：i和j是两个整数（1=i , j=30000），表示指令涉及的战舰编号。该指令是莱因哈特窃听到的杨威利发布的舰队调动指令，并且保证第i号战舰与第j号战舰不在同一列。 C i j ：i和j是两个整数（1=i , j=30000），表示指令涉及的战舰编号。该指令是莱因哈特发布的询问指令。,输出: 输出文件为galaxy.out。你的程序应当依 次对输入的每一条指令进行分析和处理： 如果是杨威利发布的舰队调动指令，则表示舰 队排列发生了变化，你的程序要注意到这一点， 但是不要输出任何信息； 如果是莱因哈特发布的询问指令，你的程序要 输出一行，仅包含一个整数，表