并查集及其应用PPT课件

《并查集及其应用PPT课件》由会员分享，可在线阅读，更多相关《并查集及其应用PPT课件（49页珍藏版）》请在金锄头文库上搜索。

1、并查集及其应用及其应用 一、引例一、引例 例一、例一、亲戚亲戚(relation)(relation) 问题描述：问题描述： 或许你并不知道，你的某个朋友是你的亲戚。他可能是你的曾祖父或许你并不知道，你的某个朋友是你的亲戚。他可能是你的曾祖父的外公的女婿的外甥女的表姐的孙子！的外公的女婿的外甥女的表姐的孙子！ 如果能得到完整的家谱，判断两个人是否亲戚应该是可行的，但如如果能得到完整的家谱，判断两个人是否亲戚应该是可行的，但如果两个人的最近公共祖先与他们相隔好几代，使得家谱十分庞大，那么果两个人的最近公共祖先与他们相隔好几代，使得家谱十分庞大，那么检验亲戚关系实非人力所能及。在这种情况下，最好的

2、帮手就是计算机。检验亲戚关系实非人力所能及。在这种情况下，最好的帮手就是计算机。为了将问题简化，你将得到一些亲戚关系的信息，如为了将问题简化，你将得到一些亲戚关系的信息，如MarryMarry和和TomTom是亲戚，是亲戚，TomTom和和BenBen是亲戚，等等。从这些信息中，你可以推出是亲戚，等等。从这些信息中，你可以推出MarryMarry和和BenBen是亲戚。是亲戚。 请写一个程序，对于我们的关于亲戚关系的提问，以最快的速度给请写一个程序，对于我们的关于亲戚关系的提问，以最快的速度给出答案。出答案。 1并查集及其应用及其应用 输入由两部分组成：输入由两部分组成： 第第一一部部分分以以

3、N N，M M开开始始。N N为为问问题题涉涉及及的的人人的的个个数数(1 (1 N N 20000)20000)。这这些些人人的的编编号号为为1,2,3, 1,2,3, N N。下下面面有有M M行行(1 (1 M M 1 1 000 000 000)000)，每每行行有有两两个个数数a ai i, b, bi i，表示已知，表示已知a ai i和和b bi i是亲戚。是亲戚。 第第二二部部分分以以Q Q开开始始。以以下下Q Q行行有有Q Q个个询询问问(1 (1 Q Q 1 1 000 000 000)000)，每每行行为为c ci i, , d di i，表示询问，表示询问c ci i和

4、和d di i是否为亲戚。是否为亲戚。 输出：输出： 对对于于每每个个询询问问c ci i, , d di i，输输出出一一行行：若若c ci i和和d di i为为亲亲戚戚，则则输输出出“Yes”“Yes”，否则输出否则输出“No”“No”。 2并查集及其应用及其应用 输入样例（输入样例（relation.inrelation.in）：）：10 710 72 42 45 75 71 31 38 98 91 21 25 65 62 32 33 33 43 47 107 108 98 9输出样例（输出样例（relation.outrelation.out）：）：YesYesNoNoYesYes

5、3并查集及其应用及其应用 问题分析：问题分析： 将每个人抽象成为一个点，数据给出将每个人抽象成为一个点，数据给出M M个边的关系，两个人个边的关系，两个人是亲戚的时候两点间有一条边。很自然的就得到了一个是亲戚的时候两点间有一条边。很自然的就得到了一个N N个顶点个顶点M M条边的图论模型，注意到传递关系，在图中一个连通块中的任条边的图论模型，注意到传递关系，在图中一个连通块中的任意点之间都是亲戚。对于最后的意点之间都是亲戚。对于最后的Q Q个提问，即判断所提问的两个个提问，即判断所提问的两个顶点是否在同一个连通块中。顶点是否在同一个连通块中。 用传统的思路，马上可以反应过来，对于输入的用传统的

6、思路，马上可以反应过来，对于输入的N N个点个点M M条条边，找出连通块，然后进行判断。但这种实现思路首先必须保边，找出连通块，然后进行判断。但这种实现思路首先必须保存存M M条边，然后再进行普通的遍历算法，不管是从空间还是时条边，然后再进行普通的遍历算法，不管是从空间还是时间上看，效率都不高。间上看，效率都不高。 再进一步考虑，如果把题目的要求改一改，对于边和提问再进一步考虑，如果把题目的要求改一改，对于边和提问相间输入，即把题目改成：相间输入，即把题目改成： 4并查集及其应用及其应用 第一行是第一行是N N，M M。N N为问题涉及的人的个数为问题涉及的人的个数(1 (1 N N 2000

7、0) 20000)。这些人的编号为这些人的编号为1,2,3, N1,2,3, N。 下面有下面有M M行行(1 (1 M M 2 000 000) 2 000 000)，每行有三个数，每行有三个数k ki i,a,ai i, b, bi i, ,a ai i和和b bi i表示两个元素，表示两个元素，k ki i为为0 0或或1 1，k ki i为为1 1时表示这是一条边的信息，时表示这是一条边的信息，即即a a表示表示i i和和b bi i是亲戚关系；是亲戚关系；k ki i为为0 0时表示这是一个提问，要你根据时表示这是一个提问，要你根据此行以前所得到的信息，判断此行以前所得到的信息，判断

8、a ai i和和b bi i是否是亲戚，对于每条提问是否是亲戚，对于每条提问回答回答YesYes或者或者NoNo。 这个问题比原问题更复杂些，需要在任何时候回答提问的两这个问题比原问题更复杂些，需要在任何时候回答提问的两个人的关系，并且对于信息提示还要能立即合并两个连通块。采个人的关系，并且对于信息提示还要能立即合并两个连通块。采用连通图思想显然在实现上就有所困难，因为要实时地表示人与用连通图思想显然在实现上就有所困难，因为要实时地表示人与人之间的关系。人之间的关系。 5并查集及其应用及其应用 用集合的思路，对于每个人建立一个集合，开始的时候集合用集合的思路，对于每个人建立一个集合，开始的时候

9、集合元素是这个人本身，表示开始时不知道任何人是他的亲戚。以后元素是这个人本身，表示开始时不知道任何人是他的亲戚。以后每次给出一个亲戚关系时，就将两个集合合并。这样实时地得到每次给出一个亲戚关系时，就将两个集合合并。这样实时地得到了在当前状态下的集合关系。如果有提问，即在当前得到的结果了在当前状态下的集合关系。如果有提问，即在当前得到的结果中看两元素是否属于同一集合。对于样例数据的解释如下图：中看两元素是否属于同一集合。对于样例数据的解释如下图： 6并查集及其应用及其应用 输入关系输入关系 分离集合分离集合初始状态初始状态 12345678910 12345678910(2,4) 12,4356

10、78910(2,4) 12,435678910(5,7) 12,435,768910(5,7) 12,435,768910(1,3)(1,3) 1,32,45,768910 1,32,45,768910(8,9) 1,32,45,768,910(8,9) 1,32,45,768,910(1,2) 1,2,3,45,768,910(1,2) 1,2,3,45,768,910(5,6) 1,2,3,45,6,78,910(5,6) 1,2,3,45,6,78,910(2,3) 1,2,3,45,6,78,910(2,3) 1,2,3,45,6,78,9107并查集及其应用及其应用 用集合的思路，对

11、于每个人建立一个集合，开始的时候集合用集合的思路，对于每个人建立一个集合，开始的时候集合元素是这个人本身，表示开始时不知道任何人是他的亲戚。以后元素是这个人本身，表示开始时不知道任何人是他的亲戚。以后每次给出一个亲戚关系时，就将两个集合合并。这样实时地得到每次给出一个亲戚关系时，就将两个集合合并。这样实时地得到了在当前状态下的集合关系。如果有提问，即在当前得到的结果了在当前状态下的集合关系。如果有提问，即在当前得到的结果中看两元素是否属于同一集合。对于样例数据的解释如下图：中看两元素是否属于同一集合。对于样例数据的解释如下图： 由由上上图图可可以以看看出出，操操作作是是在在集集合合的的基基础础

12、上上进进行行的的，没没有有必必要要保存所有的边，而且每一步得到的划分方式是动态的。保存所有的边，而且每一步得到的划分方式是动态的。 如何来实现以上的算法思想呢？我们就用到并查集。如何来实现以上的算法思想呢？我们就用到并查集。8并查集及其应用及其应用 二、并查集的基本思想二、并查集的基本思想 1 1、什么叫并查集、什么叫并查集 并查集（并查集（union-find setunion-find set）是一种用于分离集合操作的抽）是一种用于分离集合操作的抽象数据类型。它所处理的是象数据类型。它所处理的是“集合集合”之间的关系，即动态地维之间的关系，即动态地维护和处理集合元素之间复杂的关系，当给出两

13、个元素的一个无护和处理集合元素之间复杂的关系，当给出两个元素的一个无序对序对(a,b)(a,b)时，需要快速时，需要快速“合并合并”a”a和和b b分别所在的集合，这其分别所在的集合，这其间需要反复间需要反复“查找查找”某元素所在的集合。某元素所在的集合。“并并”、“查查”和和“集集”三字由此而来。在这种数据类型中，三字由此而来。在这种数据类型中，n n个不同的元素被分个不同的元素被分为若干组。每组是一个集合，这种集合叫做分离集合为若干组。每组是一个集合，这种集合叫做分离集合（disjoint setdisjoint set）。并查集支持查找一个元素所属的集合以及）。并查集支持查找一个元素所属

14、的集合以及两个元素各自所属的集合的合并。两个元素各自所属的集合的合并。9并查集及其应用及其应用 二、并查集的基本思想二、并查集的基本思想 例如，有这样的问题：初始时例如，有这样的问题：初始时n n个元素分属不同的个元素分属不同的n n个集合，个集合，通过不断的给出元素间的联系，要求实时的统计元素间的关系通过不断的给出元素间的联系，要求实时的统计元素间的关系（是否存在直接或间接的联系）。这时就有了并查集的用武之（是否存在直接或间接的联系）。这时就有了并查集的用武之地了。元素间是否有联系，只要判断两个元素是否属于同一个地了。元素间是否有联系，只要判断两个元素是否属于同一个集合；而给出元素间的联系，

15、建立这种联系，则只需合并两个集合；而给出元素间的联系，建立这种联系，则只需合并两个元素各自所属的集合。这些操作都是并查集所提供的。元素各自所属的集合。这些操作都是并查集所提供的。 并查集本身不具有结构，必须借助一定的数据结构以得到并查集本身不具有结构，必须借助一定的数据结构以得到支持和实现。数据结构的选择是一个重要的环节，选择不同的支持和实现。数据结构的选择是一个重要的环节，选择不同的数据结构可能会在查找和合并的操作效率上有很大的差别，但数据结构可能会在查找和合并的操作效率上有很大的差别，但操作实现都比较简单高效。并查集的数据结构实现方法很多，操作实现都比较简单高效。并查集的数据结构实现方法很

16、多，一般用的比较多的是，数组实现、链表实现和树实现。一般用的比较多的是，数组实现、链表实现和树实现。 10并查集及其应用及其应用 二、并查集的基本思想二、并查集的基本思想 并查集的数据结构记录了一组分离的动态集合并查集的数据结构记录了一组分离的动态集合S=S1,S2,SkS=S1,S2,Sk。每个集合通过一个。每个集合通过一个“代表代表”加以识别，加以识别，代表即该元素中的某个元素，哪一个成员被选做代表是无所代表即该元素中的某个元素，哪一个成员被选做代表是无所谓的，重要的是：如果求某一动态集合的代表两次，且在两谓的，重要的是：如果求某一动态集合的代表两次，且在两次请求间不修改集合，则两次得到的

17、答案应该是相同的。次请求间不修改集合，则两次得到的答案应该是相同的。 动态集合中的每一元素是由一个对象来表示的，设动态集合中的每一元素是由一个对象来表示的，设x x表示表示一个对象，并查集的实现需要支持如下操作：一个对象，并查集的实现需要支持如下操作： 2 2、并查集支持的操作、并查集支持的操作11并查集及其应用及其应用 二、并查集的基本思想二、并查集的基本思想 2 2、并查集支持的操作、并查集支持的操作 MAKE-SET MAKE-SET（x x）：建立一个新的集合，其仅有的成员（同时就）：建立一个新的集合，其仅有的成员（同时就是代表）是是代表）是x x。由于各集合是分离的，要求。由于各集合

18、是分离的，要求x x没有在其它集合中没有在其它集合中出现过。出现过。 UNION UNION（x,yx,y）：将包含）：将包含x x和和y y的动态集合（例如的动态集合（例如SxSx和和SySy）合并为）合并为一个新的集合，假定在此操作前这两个集合是分离的。结果的一个新的集合，假定在此操作前这两个集合是分离的。结果的集合代表是集合代表是SxSySxSy的某个成员。一般来说，在不同的实现中通的某个成员。一般来说，在不同的实现中通常都以常都以SxSx或者或者SySy的代表作为新集合的代表。此后，由新的集合的代表作为新集合的代表。此后，由新的集合S S代替了原来的代替了原来的SxSx和和SySy。

19、FIND-SET FIND-SET（x x）：返回一个指向包含）：返回一个指向包含x x的集合的代表。的集合的代表。 12并查集及其应用及其应用 三、并查集的实现及优化三、并查集的实现及优化 1 1、并查集的数组实现、并查集的数组实现 实现并查集的最简单的方法是用数组记录每个元素所属的实现并查集的最简单的方法是用数组记录每个元素所属的集合的编号。查找元素所属的集合时，只需读出数组中记录的集合的编号。查找元素所属的集合时，只需读出数组中记录的该元素所属集合的编号即可，时间复杂度为该元素所属集合的编号即可，时间复杂度为O(1)O(1)。合并两元素。合并两元素各自所属的集合时，需要将数组中属于其中一

20、个集合的元素所各自所属的集合时，需要将数组中属于其中一个集合的元素所对应的数组元素值全部改为另一个集合的编号值，时间复杂度对应的数组元素值全部改为另一个集合的编号值，时间复杂度为为O(n)O(n)。由于实现简单，所以实际使用的很多。由于实现简单，所以实际使用的很多。 以上的数组实现虽然很方便，但是合并的代价太大。在最以上的数组实现虽然很方便，但是合并的代价太大。在最坏情况下，所有集合合并成一个集合的总代价可以达到坏情况下，所有集合合并成一个集合的总代价可以达到O(nO(n2 2) )。 13并查集及其应用及其应用 三、并查集的实现及优化三、并查集的实现及优化 2 2、并查集的链表实现、并查集的

21、链表实现 我我们们需需要要用用一一定定的的数数据据结结构构来来组组织织动动态态的的集集合合，同同一一集集合合中中的的所所有有元元素素应应该该是是联联系系在在一一起起的的。一一种种比比较较简简单单的的想想法法是是用用链链表表来来实实现现，每每个个集集合合对对应应一一个个链链表表，它它有有一一个个表表头头，每每一一个个元元素素有有一一个个指指针针指指向向表表头头，表表明明了了它它所所属属的的类类，另另有有一一个个指指针针指指向向它它的的下下一一个个元元素素, ,同同时时为为了了方方便便实实现现，再再设设一一个个指指针针lastlast表表示示链链表表中中的的最最后后一一个个元元素素（表表尾尾）。可

22、可以以选选择择静静态态数数组组（一一般般来来说说这这种种问问题题处处理理的的对对象象都都是是连连续续整整数数，可可以以用用下下标标来来对对应应元元素素）来来实实现现，定定义义一个记录为：一个记录为：type type node = recordnode = recordhead,next,last:integer;head,next,last:integer; end; end;var S : array1.maxn of node;var S : array1.maxn of node; 14并查集及其应用及其应用 三、并查集的实现及优化三、并查集的实现及优化 2 2、并查集的链表实现、并查

23、集的链表实现 可以得到可以得到MAKE-SETMAKE-SET和和FIND-SETFIND-SET的实现为：的实现为：MAKE-SET(x)MAKE-SET(x) Sx.head = x;Sx.next = 0; Sx.head = x;Sx.next = 0; FIND-SETFIND-SET（x x） return Sx.head return Sx.head 两两个个过过程程的的时时间间复复杂杂度度都都为为O(1)O(1)。注注意意到到我我们们采采用用链链表表以以后后，当当有有两两个个元元素素(x,y),FIND-SET(x,y),FIND-SET（x x）FIND-SETFIND-SE

24、T（y y）时时，两两者者对对应应不不同同的的集集合合，需需要要将将两两个个链链表表合合并并，做做法法是是将将一一个个表表的的表表头头直直接接接接到到另另一一个个表表的的表表尾尾，这这步步操操作作很很简简单单，但但势势必必造造成成修修改改后后需需要要把把接接上上去去的的那那个个表表的的所所有有headhead值值修修改改，这这需需要要线线性性的的赋值操作，其复杂度与选择接在尾部的链表长度成正比。赋值操作，其复杂度与选择接在尾部的链表长度成正比。 15并查集及其应用及其应用 三、并查集的实现及优化三、并查集的实现及优化 2 2、并查集的链表实现、并查集的链表实现 现在讨论现在讨论UNION(x,

25、y)UNION(x,y)的实现，假设的实现，假设UNION(x,y)UNION(x,y)的参数是有序的，即把的参数是有序的，即把y y属属于的集合合并到于的集合合并到x x的集合。有两种实现方法：的集合。有两种实现方法： （1 1）简单实现）简单实现 不考虑任何因素，出现不考虑任何因素，出现FIND-SETFIND-SET（x x）FIND-SETFIND-SET（y y）时，直接将）时，直接将y y的表头的表头接到接到x x的尾，同时将的尾，同时将y y中所在集合元素所有元素的中所在集合元素所有元素的headhead设为设为FIND-SET(x)FIND-SET(x)。同时。同时x x的表尾

26、也应该设为原的表尾也应该设为原y y的表尾。注意的表尾。注意lastlast指针其实只要在表头结点中记录即可，指针其实只要在表头结点中记录即可，因为每一次查到因为每一次查到FIND-SETFIND-SET（x x）都可以得到表头元素。而链表中其他元素重新记）都可以得到表头元素。而链表中其他元素重新记录录lastlast是无意义的。是无意义的。 考虑输入数据的特殊性，我们总是把考虑输入数据的特殊性，我们总是把y y接到接到x x里去，那么如果里去，那么如果y y所在的集合非所在的集合非常大，每次赋值的代价就会非常高，比如出现输入为：常大，每次赋值的代价就会非常高，比如出现输入为： （2 2，1

27、1），（），（3 3，1 1），（），（4 4，1 1），（），（5 5，1 1），（），（6 6，1 1） ， ，(n,1)(n,1) 显然显然y y所在的集合越来越庞大，对于这种方法最坏情况下时间复杂度为所在的集合越来越庞大，对于这种方法最坏情况下时间复杂度为O(n2)O(n2)。 16并查集及其应用及其应用 三、并查集的实现及优化三、并查集的实现及优化 2 2、并查集的链表实现、并查集的链表实现 （2 2）快速实现）快速实现 上述简单实现非常不理想，针对上述简单实现非常不理想，针对y y可能比较大的这个问题，可可能比较大的这个问题，可以很快产生一个聪明的想法：不妨比较以很快产生一个聪明的

28、想法：不妨比较x x和和y y所在集合的大小，从所在集合的大小，从而作出选择，把较短的链表接在较长的尾部，这样效果是一样的，而作出选择，把较短的链表接在较长的尾部，这样效果是一样的，但耗费肯定不比原来差。这就是快速实现的思路。可以在但耗费肯定不比原来差。这就是快速实现的思路。可以在nodenode里里多设一个域多设一个域numbernumber，用来记录此条链表中成员的个数。显然，用来记录此条链表中成员的个数。显然numbernumber记录在表头元素中即可，将两表合并的时候，只要将表的记录在表头元素中即可，将两表合并的时候，只要将表的numbernumber相加，因此维护起来是非常方便的。相

29、加，因此维护起来是非常方便的。 这种快速实现的方法可以称为加权启发式合并，这里的权就这种快速实现的方法可以称为加权启发式合并，这里的权就是指所记录的是指所记录的numbernumber。 17并查集及其应用及其应用 三、并查集的实现及优化三、并查集的实现及优化 2 2、并查集的链表实现、并查集的链表实现 可以证明这种方法的效率。当有可以证明这种方法的效率。当有n n个元素时，在个元素时，在UNIONUNION上的上的花费（即重新赋值的次数）的上界是花费（即重新赋值的次数）的上界是O(nlogO(nlog2 2n)n)。考虑一个固定。考虑一个固定的对象的对象x x，当，当x x的代表指针（的代表

30、指针（headhead）被更新时，）被更新时，x x必是属于一个必是属于一个较小的集合，因此，较小的集合，因此，x x的代表指针第一次更新后，结果集合必的代表指针第一次更新后，结果集合必然至少有然至少有2 2个元素，类似的，下一次更新后，个元素，类似的，下一次更新后，x x所在的集合至少所在的集合至少有有4 4个元素。继续下去，可以发现，个元素。继续下去，可以发现，x x的代表指针最多被更新的代表指针最多被更新loglog2 2n n次，因为当次，因为当x x所在集合元素已经等于所在集合元素已经等于n n以后，不可能再发生以后，不可能再发生UNIONUNION操作。所以，总共有操作。所以，总共

31、有n n个元素时，操作的总次数不超过个元素时，操作的总次数不超过nlognlog2 2n n次。这就保证了整个算法的复杂度是理想的。次。这就保证了整个算法的复杂度是理想的。 18并查集及其应用及其应用 三、并查集的实现及优化三、并查集的实现及优化 2 2、并查集的链表实现、并查集的链表实现 合并两个集合时的实现过程如下：合并两个集合时的实现过程如下：UNION(x,y) UNION(x,y) x = FIND-SET(x); x = FIND-SET(x); y = FIND-SET(y); y = FIND-SET(y); if x.numbery.number then UNION(x,y

32、) if x.numbery.number then UNION(x,y) else UNION(y,x); else UNION(y,x); 并查集的链表实现是一种非常容易接受的算法，并且它并查集的链表实现是一种非常容易接受的算法，并且它的效率也是令人满意的。其实它的思路和数组完全一样，所的效率也是令人满意的。其实它的思路和数组完全一样，所以实际使用较少。以实际使用较少。 19并查集及其应用及其应用 三、并查集的实现及优化三、并查集的实现及优化 3 3、并查集的树实现、并查集的树实现 实实现现并并查查集集的的另另一一种种方方法法是是利利用用树树。我我们们用用有有根根树树来来表表示示集集合合，

33、树树中中的的每每个个节节点点包包含含集集合合的的一一个个成成员员，每每棵棵树树表表示示一一个个集集合合。多多个个集集合合形形成成森森林林态态，以以每每棵棵树树的的树树根根作作为为集集合合的的代代表表，并并且且根根结结点点的的父父结结点点指指向向其其自自身身，树树上上的的其其他他结结点点都都用用一一个个父父指针表示它的附属关系。指针表示它的附属关系。 注注意意：在在同同一一棵棵树树中中的的结结点点属属于于同同一一个个集集合合，虽虽然然它它们们在在树树中中存存在在父父子子结结点点关关系系，但但并并不不意意味味着着它它们们之之间间存存在在从从属属关关系系。树的指针起的只是联系集合中元素的作用。树的指

34、针起的只是联系集合中元素的作用。 在并查集中，每个分离集合对应的一棵树，称为分离集合在并查集中，每个分离集合对应的一棵树，称为分离集合树。整个并查集也就是一棵分离集合森林。树。整个并查集也就是一棵分离集合森林。 20并查集及其应用及其应用 三、并查集的实现及优化三、并查集的实现及优化 3 3、并查集的树实现、并查集的树实现 下图表示了这种关系，其包含两个集合下图表示了这种关系，其包含两个集合b,c,e,h,d,f,gb,c,e,h,d,f,g分分别以别以c c和和f f作为代表。作为代表。 21并查集及其应用及其应用 三、并查集的实现及优化三、并查集的实现及优化 3 3、并查集的树实现、并查集

35、的树实现 这种树结构也可以简单地用静态数组实现，设这种树结构也可以简单地用静态数组实现，设pxpx表示表示x x元素所指向的父亲。元素所指向的父亲。MAKE-SET(x)MAKE-SET(x)：px=x;px=x;FIND-SET(x)FIND-SET(x)：要从：要从x x开始，向上寻找它的父亲，直到找到根为止。开始，向上寻找它的父亲，直到找到根为止。UNIONUNION（x,yx,y）：只要使一棵树的根指向另一棵树的根，即成为一棵子树。）：只要使一棵树的根指向另一棵树的根，即成为一棵子树。 可以发现，元素之间的联系是靠指针来实现的，与链表的实现相比，所可以发现，元素之间的联系是靠指针来实现

36、的，与链表的实现相比，所需要进行的修改少了许多。但可以发现，需要进行的修改少了许多。但可以发现，UNIONUNION（x,yx,y）虽然是简便了许多，）虽然是简便了许多，但是但是FIND-SETFIND-SET（x x）则需要从）则需要从x x开始，经过一条可能比较长的路径，才能找到开始，经过一条可能比较长的路径，才能找到树根。具体实现如下：树根。具体实现如下： 22并查集及其应用及其应用 三、并查集的实现及优化三、并查集的实现及优化 3 3、并查集的树实现、并查集的树实现 (1)(1)查找一个元素所属的集合查找一个元素所属的集合 在在分分离离集集合合森森林林中中，每每一一棵棵分分离离集集合合

37、树树对对应应一一个个集集合合。要要查查找找某某一一元元素素所属的集合，就是要找这个元素对应的结点所在的分离集合树。所属的集合，就是要找这个元素对应的结点所在的分离集合树。 不不妨妨以以分分离离集集合合树树的的根根结结点点的的编编号号来来表表示示这这个个分分离离集集合合树树。这这样样，查查找找一个结点所在的分离集合树，也就是查找该结点所在分离集合树的根结点了。一个结点所在的分离集合树，也就是查找该结点所在分离集合树的根结点了。 查找树的根结点的方法很简单，只需任取树中一结点（不妨就取我们要查找树的根结点的方法很简单，只需任取树中一结点（不妨就取我们要查找的那个结点），沿父结点方向一直往树根走：初

38、始时，取一个结点，走查找的那个结点），沿父结点方向一直往树根走：初始时，取一个结点，走到它的父结点，然后以父结点为基点，走到父结点的父结点到它的父结点，然后以父结点为基点，走到父结点的父结点直至走到一直至走到一个没有父结点的结点为止，这个结点就是树的根结点。个没有父结点的结点为止，这个结点就是树的根结点。 23并查集及其应用及其应用 三、并查集的实现及优化三、并查集的实现及优化 3 3、并查集的树实现、并查集的树实现 (1)(1)查找一个元素所属的集合查找一个元素所属的集合下图描述了查找一个结点的过程（黑色结点为当前查找结点）。下图描述了查找一个结点的过程（黑色结点为当前查找结点）。 查找算法

39、的复杂度取决于查找结点的深度，假设查找结点的深度为查找算法的复杂度取决于查找结点的深度，假设查找结点的深度为h h，则算法的时间复杂度为则算法的时间复杂度为O(h)O(h)。 24并查集及其应用及其应用 三、并查集的实现及优化三、并查集的实现及优化 3 3、并查集的树实现、并查集的树实现 (2)(2)两个元素各自所属的集合的合并两个元素各自所属的集合的合并 在分离集合森林中，分离集合是用分离集合树来表示的。要合并两个元在分离集合森林中，分离集合是用分离集合树来表示的。要合并两个元素各自所属的集合，也就是合并两元素所对应的两个结点各自所在的分离集素各自所属的集合，也就是合并两元素所对应的两个结点

40、各自所在的分离集合树。合树。 现在的问题就是如何合并两棵分离集合树。考虑到在分离集合森林中，现在的问题就是如何合并两棵分离集合树。考虑到在分离集合森林中，只要结点属于同一棵树，即被视为在同一个集合中，而不管具体是如何相连只要结点属于同一棵树，即被视为在同一个集合中，而不管具体是如何相连的。那么，我们只需简单的将一棵分离集合树作为另一棵的子树，即可使两的。那么，我们只需简单的将一棵分离集合树作为另一棵的子树，即可使两棵树合并为一棵。棵树合并为一棵。 如下图，描述的是将两棵分离集合树如下图，描述的是将两棵分离集合树D D1 1和和D D2 2合并的过程（合并的过程（D D1 1作为作为D D2 2

41、的根结的根结点的一棵子树）。点的一棵子树）。 25并查集及其应用及其应用 三、并查集的实现及优化三、并查集的实现及优化 3 3、并查集的树实现、并查集的树实现 (2)(2)两个元素各自所属的集合的合并两个元素各自所属的集合的合并 要完成上述合并，首先要找到两棵分离集合树的根结点，这可以通过调用要完成上述合并，首先要找到两棵分离集合树的根结点，这可以通过调用两次查找算法得到。得到根结点后，只需改变其中一个根结点，令它的父结点两次查找算法得到。得到根结点后，只需改变其中一个根结点，令它的父结点为另一个根结点即可，代价为为另一个根结点即可，代价为O(1)O(1)。因此，整个合并算法的复杂度主要在查找

42、。因此，整个合并算法的复杂度主要在查找根结点部分，为根结点部分，为O(h)O(h)。 26并查集及其应用及其应用 三、并查集的实现及优化三、并查集的实现及优化 3 3、并查集的树实现、并查集的树实现 (3)(3)优化查找与合并算法优化查找与合并算法 前前面面提提到到，分分离离集集合合森森林林的的查查找找与与合合并并的的时时间间复复杂杂度度都都是是O(h)O(h)。也也就就是是说说，查查找找与与合合并并的的时时间间复复杂杂度度主主要要取取决决于于树树的的深深度度。就就平平均均情情况况而而言言，树树的的深深度度应应该该在在lognlogn的的数数量量级级，n n为为结结点点个个数数，所所以以分分离

43、离集集合合森森林林查查找找与与合合并并的的平平均均时时间间复复杂杂度度为为O(logn)O(logn)。但但是是，在在最最坏坏情情况况下下，一一棵棵树树的的深深度度可可能能达达到到n n，如如右右图图。这这时时的的查查找找与与合合并并的的时时间间复复杂杂度度都都达达到到了了O(n)O(n)。这这是是我我们们不不愿愿意意看看到到的的，因因此此必必须想方设法避免出现这种情况。须想方设法避免出现这种情况。 为了提高效率，可以考虑在为了提高效率，可以考虑在UNION(x,y)UNION(x,y)和和FIND-FIND-SET(x)SET(x)上作一些文章。上作一些文章。 27并查集及其应用及其应用 三

44、、并查集的实现及优化三、并查集的实现及优化 3 3、并查集的树实现、并查集的树实现 (3)(3)优化查找与合并算法优化查找与合并算法优化合并过程优化合并过程 分析一下前面那棵深度为分析一下前面那棵深度为n n的分离集合树的形成过程，可以的分离集合树的形成过程，可以看出，这是合并不当的后果。当看出，这是合并不当的后果。当合并右图的两棵分离集合树（合并右图的两棵分离集合树（A A，B B）时，显然将）时，显然将B B树作为树作为A A树根树根结点的子树得到的树比较平衡，结点的子树得到的树比较平衡，如下图中的如下图中的C C树（树（D D树为树为A A树作为树作为B B树根结点的子树得到的树）。树根

45、结点的子树得到的树）。 28并查集及其应用及其应用 三、并查集的实现及优化三、并查集的实现及优化 3 3、并查集的树实现、并查集的树实现 (3)(3)优化查找与合并算法优化查找与合并算法优化合并过程优化合并过程 一一棵棵较较平平衡衡的的树树拥拥有有比比较较低低的的深深度度，查查找找和和合合并并的的复复杂杂度度也也就就相相应应得得较较低低。因因此此，如如果果两两棵棵分分离离集集合合树树A A和和B B，深深度度分分别别为为h hA A和和h hB B，则则若若h hA AhhB B，应应将将B B树树作作为为A A树树的的子子树树；否否则则，将将A A树树作作为为B B树树的的子子树树。总总之之

46、，总总是是深深度度较较小小的的分分离离集集合合树树作作为为子子树树。得得到到的的新新的的分分离离集集合合树树C C的的深深度度h hC C，以以B B树树作作A A树树的的子树为例，子树为例，h hC C=maxh=maxhA A,h,hB B+1+1。 这样合并得到的分离集合树，其深度不会超过这样合并得到的分离集合树，其深度不会超过lognlogn，是一个比较平衡，是一个比较平衡的树。因此，查找与合并的时间复杂度也就稳定在的树。因此，查找与合并的时间复杂度也就稳定在O(logn)O(logn)了。了。 29并查集及其应用及其应用 三、并查集的实现及优化三、并查集的实现及优化 3 3、并查集的

47、树实现、并查集的树实现 (3)(3)优化查找与合并算法优化查找与合并算法优化查找过程优化查找过程 对对于于查查找找过过程程有有两两个个方方面面的的启启发发式式方方法法都都很很有有效效，分分别别是是按按秩秩合合并并和和路路径径压缩优化。压缩优化。 30并查集及其应用及其应用 A A按秩合并按秩合并 可以联系一下链表的优化，我们是选择比较小的一个集合归并到大的集合可以联系一下链表的优化，我们是选择比较小的一个集合归并到大的集合里去。对于有根树的结构，很类似地，也可以记录树上的节点数，将较小的里去。对于有根树的结构，很类似地，也可以记录树上的节点数，将较小的树的根指向较大的树。但是有根树的结构又有非

48、常特殊的地方，它的一个节树的根指向较大的树。但是有根树的结构又有非常特殊的地方，它的一个节点下面可能挂有很多子树；从前面分析也可以看出，主要的时间花在了点下面可能挂有很多子树；从前面分析也可以看出，主要的时间花在了FIND-SETFIND-SET（x x）上，只要使得树中不存在一条偏长的路径，即使得各条路径）上，只要使得树中不存在一条偏长的路径，即使得各条路径的长度都比较平均了，那么算法就不会出现特别退化的情况。对每个结点，的长度都比较平均了，那么算法就不会出现特别退化的情况。对每个结点，用一个秩（用一个秩（rankrank）来近似子树大小对数，同时它也是该节点高度的一个上界。）来近似子树大小

49、对数，同时它也是该节点高度的一个上界。进行进行UNIONUNION的时候，只要让具有较小秩的根指向具有较大秩的根。如果两根的时候，只要让具有较小秩的根指向具有较大秩的根。如果两根的秩相等，只要使其中一个根指向另一个，同时秩应当增加的秩相等，只要使其中一个根指向另一个，同时秩应当增加1 1。这十分类似。这十分类似于统计节点个数，但这里统计的是树的深度。于统计节点个数，但这里统计的是树的深度。 31并查集及其应用及其应用 B B路径压缩优化方法路径压缩优化方法 在在分分离离集集合合森森林林中中，分分离离集集合合是是用用分分离离集集合合树树来来表表示示的的。分分离离集集合合树树是是用用来来联联系系集

50、集合合中中的的元元素素的的，只只要要同同一一集集合合中中的的元元素素在在同同一一棵棵树树上上，不不管管它它们们在在树树中中是是如如何何被被联联系系的的，都都满满足足分分离离集集合合树树的的要要求求。如如下下图图，这这两两棵棵分分离离集集合合树树是是等等价价的的，因因为为它它们们所所包包含含的的元元素素相相同同。显显然然，右右边边那那棵棵树树比比较较“优优秀秀”，因因为为它它具具有有比比较较低低的的深深度度，相相应应的的，查查找找与与合合并并的的时时间间复复杂杂度度也也较较低低。那那么，我们就应该使分离集合树尽量向右树的形式靠拢。么，我们就应该使分离集合树尽量向右树的形式靠拢。 32并查集及其应

51、用及其应用 在在查查找找一一个个结结点点所所在在树树的的根根结结点点的的过过程程中中，要要经经过过一一条条从从待待查查结结点点到到根根结结点点的的路路径径。我我们们不不妨妨就就让让这这些些路路径径上上的的结结点点直直接接指指向向根根结结点点，作作为为根根结结点点的的子子结结点点。这这样样，这这些些路路径径上上的的结结点点仍仍在在分分离离集集合合中中，整整棵棵树树仍仍然然满满足足分分离离集集合合树树的的要要求求，而而路路径径上上的的结结点点的的深深度度无无疑疑降降低低了了，这这些些点点及及其其子子树树上上的的结结点点的的查查找找复复杂杂度度大大大大降降低低。如如下下图图，描描述述了了在在一一棵棵

52、分分离离集集合合树树查查找找结结点点7 7的的前后所呈现出的结构。前后所呈现出的结构。 33并查集及其应用及其应用 这这种种改改变变结结点点所所指指方方向向以以降降低低结结点点深深度度，从从而而缩缩短短查查找找路路径径长长度度的的方方法法，叫叫做做路路径径压压缩缩。实实现现路路径径压压缩缩的的最最简简单单的的方方法法是是在在查查找找从从待待查查结结点点到到根根结结点点的的路路径径时时走走两两遍遍，第第一一遍遍找找到到树树的的根根结结点点，第第二二遍遍改改变变路路径径上上结结点点指指向向根根结结点（使它们的父结点为根结点）。点（使它们的父结点为根结点）。 使使用用路路径径压压缩缩大大大大提提高高

53、了了查查找找算算法法的的效效率率。如如果果将将带带路路径径压压缩缩的的查查找找算算法法与与优优化化过过的的合合并并算算法法联联合合使使用用，则则可可以以证证明明，n n次次查查找找最最多多需需要要用用O(n(n)O(n(n)时时间间。(n)(n)是是单单变变量量阿阿克克曼曼函函数数的的逆逆函函数数，它它是是一一个个增增长长速速度度比比lognlogn慢慢的的多多但但又又不不是是常常数数的的函函数数，在在一一般般情情况况下下(n)4(n)4，可可以以当当作作常常数数看。看。 这种方法是在这种方法是在FIND-SET(x)FIND-SET(x)过程中作一些改进。设想，从过程中作一些改进。设想，从x

54、 x到它的根，我到它的根，我们必须经过一条路径，显然这条路径上的所有的根与们必须经过一条路径，显然这条路径上的所有的根与x x的根是同一个根，那么的根是同一个根，那么不妨在得到结果的同时，顺便把这条路上全部节点的根都改成不妨在得到结果的同时，顺便把这条路上全部节点的根都改成x x的根，也就是的根，也就是说，对这些节点进行了分散，其结果是，下一次如果再有这条路上的点进行说，对这些节点进行了分散，其结果是，下一次如果再有这条路上的点进行FIND-SET(x)FIND-SET(x)时，只要经过一步就可以找到根。可以认为是时，只要经过一步就可以找到根。可以认为是x x顺便帮了帮大家顺便帮了帮大家的忙，

55、把好处带给了大家，因此其它节点以后都省事了。的忙，把好处带给了大家，因此其它节点以后都省事了。 34并查集及其应用及其应用 FIND-SET(x) FIND-SET(x) 35并查集及其应用及其应用 使用这两种方法优化后的代码：使用这两种方法优化后的代码： MAKE-SET(x) MAKE-SET(x) px:=x px:=x；rankx:=0rankx:=0； UNION(x,y) UNION(x,y) x:= FIND-SET(x) x:= FIND-SET(x)；y:= FIND-SET(Y)y:= FIND-SET(Y)； if rankx ranky then py:= x if r

56、ankx ranky then py:= x else px:= y else px:= y if rankx = ranky if rankx = ranky then ranky := ranky+1; then ranky := ranky+1; FIND-SET(x) FIND-SET(x) if xpx then px:= FIND-SET(px) if xpx then px:= FIND-SET(px)； return px return px； 36并查集及其应用及其应用 可可以以看看到到FIND-SET(x)FIND-SET(x)是是一一个个递递归归的的过过程程。它它的的实实

57、现现非非常简洁，同时我们的方法也可以保证递归深度不会很深。常简洁，同时我们的方法也可以保证递归深度不会很深。 事事实实上上只只要要使使用用这这两两种种方方法法中中的的任任何何一一种种，算算法法的的效效率率都都会会大大大大提提高高。当当两两种种方方法法结结合合起起来来以以后后，效效率率更更高高，几乎可以接近几乎可以接近n n的线性复杂度。的线性复杂度。 四、引例的实现程序四、引例的实现程序1 1、数组实现、数组实现(relation1.pas) (relation1.pas) 2 2、链表实现、链表实现(relation2.pas) (relation2.pas) 3 3、树实现、树实现(rel

58、ation3.pas) (relation3.pas) 37并查集及其应用及其应用 五、应用举例五、应用举例 并查集可以作为一些复杂问题的一部分，甚至有一些特殊的应用。这里只并查集可以作为一些复杂问题的一部分，甚至有一些特殊的应用。这里只举一些最浅显的应用例子。举一些最浅显的应用例子。 例二、例二、 食物链（食物链（NOI2001 - eatNOI2001 - eat）问题描述：问题描述： 动物王国中有三类动物动物王国中有三类动物A,B,CA,B,C，这三类动物的食物链构成了有趣的环形。，这三类动物的食物链构成了有趣的环形。A A吃吃B B， B B吃吃C C，C C吃吃A A。现有。现有N

59、N个动物，以个动物，以1 1N N编号。每个动物都是编号。每个动物都是A,B,CA,B,C中的一中的一种，但是我们并不知道它到底是哪一种。有人用两种说法对这种，但是我们并不知道它到底是哪一种。有人用两种说法对这N N个动物所构成个动物所构成的食物链关系进行描述：的食物链关系进行描述： 第一种说法是第一种说法是“1 X Y”“1 X Y”，表示，表示X X和和Y Y是同类。是同类。 第二种说法是第二种说法是“2 X Y”“2 X Y”，表示，表示X X吃吃Y Y。 此人对此人对N N个动物，用上述两种说法，一句接一句的说出个动物，用上述两种说法，一句接一句的说出K K句话，句话，这这K K句话有

60、的是真的，有的是假的。句话有的是真的，有的是假的。 38并查集及其应用及其应用 你从头开始一句一句的读入这你从头开始一句一句的读入这K K句话。当你读到的话满足下列三条之一时，句话。当你读到的话满足下列三条之一时，这句话就是假的，否则就是真的。这句话就是假的，否则就是真的。 1 1） 当前的话与前面的某些真的话冲突；当前的话与前面的某些真的话冲突； 2 2） 当前的话中当前的话中X X或或Y Y比比N N大；大； 3 3） 当前的话表示当前的话表示X X吃吃X X。 你的任务是根据给定的你的任务是根据给定的N N（1=N=50,0001=N=50,000）和）和K K个条件（个条件（0=K=1

61、00,0000=K=100,000），），输出假话的总数。输出假话的总数。 输入文件（输入文件（eat.ineat.in）：）： 第一行是两个整数第一行是两个整数N N和和K K，以一个空格分隔。，以一个空格分隔。 以下以下K K行每行是三个正整数行每行是三个正整数DD，X X，Y Y，之间用一个空格隔开，其中，之间用一个空格隔开，其中D D表示表示说法的种类。若说法的种类。若D=1D=1，X X和和Y Y是同类。若是同类。若D=2D=2，X X吃吃Y Y。 输出文件（输出文件（eat.outeat.out）：）： 一个整数，表示假话的数目。一个整数，表示假话的数目。 39并查集及其应用及其应

62、用 输入样例：输入样例：100 7100 71 101 1 /1 101 1 /假假2 1 2 /2 1 2 /真真2 2 3 /2 2 3 /真真2 3 3 /2 3 3 /假假1 1 3 /1 1 3 /假假2 3 1 /2 3 1 /真真1 5 5 /1 5 5 /真真输出样例输出样例: :3 340并查集及其应用及其应用 算法分析：算法分析： 本题和亲戚问题其实是差不多的，两者的数学模型已经不能再相似了。它本题和亲戚问题其实是差不多的，两者的数学模型已经不能再相似了。它就相当于例一中提出的亲戚问题的第就相当于例一中提出的亲戚问题的第2 2版，即边合并还需要边判断。本题的难版，即边合并还

63、需要边判断。本题的难点恐怕在于两个点的关系不仅是同集合的关系，还涉及到在同一集合中处于怎点恐怕在于两个点的关系不仅是同集合的关系，还涉及到在同一集合中处于怎样的捕食关系，显然在同一个集合中还需要对各种动物进行标号。用样的捕食关系，显然在同一个集合中还需要对各种动物进行标号。用0 0，1 1，2 2对每种动物染色，如下图所示：对每种动物染色，如下图所示： 如果两个动物如果两个动物x x和和y y同类，同类， 则则colorx=colory;colorx=colory;如果如果x x吃吃y y， 那么那么(colorx+1)mod 3=colory(colorx+1)mod 3=colory。 4

64、1并查集及其应用及其应用 这时对两个集合这时对两个集合UNIONUNION（x,yx,y）进行合并时就需要做更多的工作。假定）进行合并时就需要做更多的工作。假定x x集合颜色不变，那么要把集合颜色不变，那么要把y y集合并到集合并到x x集合中，集合中，y y集合的每个元素只要全部相集合的每个元素只要全部相应增加某一个增值应增加某一个增值d d，就可以把，就可以把x x，y y统一起来了。例如统一起来了。例如x x和和y y属于同类，而属于同类，而colorx=2colorx=2，colory=1colory=1，y y集合中所有元素的颜色都增加集合中所有元素的颜色都增加1 1（mod 3mo

65、d 3），两），两集合元素的颜色就统一了。集合元素的颜色就统一了。 考虑该算法的实现。前面的讨论中，可知用有根树来实现效率是非常考虑该算法的实现。前面的讨论中，可知用有根树来实现效率是非常高的，但高效的方法未必好用，比如对于此题，如果采用有根树的直接实高的，但高效的方法未必好用，比如对于此题，如果采用有根树的直接实现，由于元素之间存在染色的转换，那么维护有根树时，树内动物之间的现，由于元素之间存在染色的转换，那么维护有根树时，树内动物之间的关系无法及时明确。事实上本题可以简单地采用链表实现的方法，前面已关系无法及时明确。事实上本题可以简单地采用链表实现的方法，前面已经说了，只要将经说了，只要将

66、y y里面的元素进行一下调整，链表实现中本来就需要对里面的元素进行一下调整，链表实现中本来就需要对y y集集合里每个节点的代表指针进行调整，因此此步改变只需要在原算法中稍作合里每个节点的代表指针进行调整，因此此步改变只需要在原算法中稍作添加，不需要更进一步的复杂讨论了。添加，不需要更进一步的复杂讨论了。 42并查集及其应用及其应用 例三、求无向图的连通分量例三、求无向图的连通分量 这个问题其实在例一中已经提过了。这里再单独提出来强调一下，因这个问题其实在例一中已经提过了。这里再单独提出来强调一下，因为求无向图连通分量是个非常常用的算法。通过并查集可以使得空间上省为求无向图连通分量是个非常常用的

67、算法。通过并查集可以使得空间上省去对边的保存，同时时间效率又是很高的。去对边的保存，同时时间效率又是很高的。 需要特别指出的是，如果用链表来实现的话，最后任何在同一个集合需要特别指出的是，如果用链表来实现的话，最后任何在同一个集合（即连通块）中的元素，其代表指针的值都是相等的。而采用有根树来实（即连通块）中的元素，其代表指针的值都是相等的。而采用有根树来实现的话，算法结束后，留下的依然是树的关系，因此如果希望每个元素都现的话，算法结束后，留下的依然是树的关系，因此如果希望每个元素都指向它的根的话，还需要对每个节点进行一次指向它的根的话，还需要对每个节点进行一次FIND-SETFIND-SET操

68、作，这样每个节操作，这样每个节点的父节点都是代表此集合的节点。在某些统计问题中，往往需要这样做。点的父节点都是代表此集合的节点。在某些统计问题中，往往需要这样做。而从另一方面讲，有根树的实现，如果忽略而从另一方面讲，有根树的实现，如果忽略“按秩合并按秩合并”这一优化，时间这一优化，时间效率依然是很高的，但可以省去效率依然是很高的，但可以省去RANKRANK这个线性空间的保存。因此在某些时这个线性空间的保存。因此在某些时候如果内存紧张的话，是可以以牺牲时间来换取空间的。候如果内存紧张的话，是可以以牺牲时间来换取空间的。 43并查集及其应用及其应用 例四、例四、KruskalKruskal最小生成

69、树算法最小生成树算法此经典算法的思想是将树上的边按照权排序，然后从此经典算法的思想是将树上的边按照权排序，然后从小到大分析每一条边，如果选到一条边小到大分析每一条边，如果选到一条边e=(v1,v2),e=(v1,v2),且且v1v1和和v2v2不在一个连通块中，就将不在一个连通块中，就将e e作为最小生成树的一条边，否则作为最小生成树的一条边，否则忽略忽略e e。这其中明显就包含了并查集的算法。这其中明显就包含了并查集的算法。KruskalKruskal算法也算法也只有在结合了并查集后才能说是个有效的算法。只有在结合了并查集后才能说是个有效的算法。 44并查集及其应用及其应用 六、小结六、小结

70、 并查集的三种实现都是简单而高效的。对于某些具体的问并查集的三种实现都是简单而高效的。对于某些具体的问题，到底用怎样的实现，是需要进一步推敲的。不管怎么说它题，到底用怎样的实现，是需要进一步推敲的。不管怎么说它只是一种底层的数据结构，它的实现应该和具体问题的特征结只是一种底层的数据结构，它的实现应该和具体问题的特征结合在一起。合在一起。 另外考察并查集的分析方法：首先我们提出用集合来实现另外考察并查集的分析方法：首先我们提出用集合来实现元素之间关系，然后，我们考察它需要支持的操作，接着是具元素之间关系，然后，我们考察它需要支持的操作，接着是具体的实现，对于不同的实现，又有针对性地进行优化。设想

71、体的实现，对于不同的实现，又有针对性地进行优化。设想, ,分析分析, ,优化优化, ,推广推广, ,这是分析数据结构一般的方法。另一方面，这是分析数据结构一般的方法。另一方面，并查集的优化主要依靠启发式，这一点在思考问题的时候也是并查集的优化主要依靠启发式，这一点在思考问题的时候也是常用的，实际上就是这点简单的启发，将随意的过程有意化，常用的，实际上就是这点简单的启发，将随意的过程有意化，大幅度地提高了效率，避免了性能上的退化。大幅度地提高了效率，避免了性能上的退化。 45并查集及其应用及其应用 七、作业七、作业作业作业1 1、家谱、家谱(GEN,(GEN,时间限制时间限制:2S):2S)问题

72、描述问题描述: : 现代的人对于本家族血统越来越感兴趣，现在给出充足的父子关系，请你编写现代的人对于本家族血统越来越感兴趣，现在给出充足的父子关系，请你编写程序找到某个人的最早的祖先。程序找到某个人的最早的祖先。输入输入: : 输入文件由多行组成，首先是一系列有关父子关系的描述，其中每一组父子关系输入文件由多行组成，首先是一系列有关父子关系的描述，其中每一组父子关系由二行组成，用由二行组成，用#name#name的形式描写一组父子关系中的父亲的名字，用的形式描写一组父子关系中的父亲的名字，用+name+name的形式描写的形式描写一组父子关系中的儿子的名字；接下来用一组父子关系中的儿子的名字；

73、接下来用?name?name的形式表示要求该人的最早的祖先；的形式表示要求该人的最早的祖先；最后用单独的一个最后用单独的一个$ $表示文件结束。表示文件结束。 规定每个人的名字都有且只有规定每个人的名字都有且只有6 6个字符，而且首字母大写，且没有任意两个人的名个字符，而且首字母大写，且没有任意两个人的名字相同。最多可能有字相同。最多可能有10001000组父子关系，总人数最多可能达到组父子关系，总人数最多可能达到5000050000人，家谱中的记载不人，家谱中的记载不超过超过3030代。代。输出输出: : 按照输入文件的要求顺序，求出每一个要找祖先的人的祖先，按照输入文件的要求顺序，求出每一

74、个要找祖先的人的祖先，格式：本人的名字格式：本人的名字+ +一个空格一个空格+ +祖先的名字祖先的名字+ +回车。回车。 46并查集及其应用及其应用 样例输入：样例输入：GEN.INGEN.IN#George#George+Rodney+Rodney#Arthur#Arthur+Gareth+Gareth+Walter+Walter#Gareth#Gareth+Edward+Edward?Edward?Edward?Walter?Walter?Rodney?Rodney?Arthur?Arthur$ $样例输出：样例输出：GEN.OUTGEN.OUTEdward ArthurEdward Ar

75、thurWalter ArthurWalter ArthurRodney GeorgeRodney GeorgeArthur Arthur Arthur Arthur 47并查集及其应用及其应用 作业作业2 2、团伙、团伙(group(group，时间限制：，时间限制：2S)2S)问题描述：问题描述： 在某城市里住着在某城市里住着n n个人，任何两个认识的人不是朋友就是敌人，而且满足：个人，任何两个认识的人不是朋友就是敌人，而且满足：1 1、 我朋友的朋友是我的朋友；我朋友的朋友是我的朋友；2 2、 我敌人的敌人是我的朋友；我敌人的敌人是我的朋友； 所有是朋友的人组成一个团伙。告诉你关于这所有

76、是朋友的人组成一个团伙。告诉你关于这n n个人的个人的m m条信息，即某两个人是条信息，即某两个人是朋友，或者某两个人是敌人，请你编写一个程序，计算出这个城市最多可能有多少朋友，或者某两个人是敌人，请你编写一个程序，计算出这个城市最多可能有多少个团伙？个团伙？输入：输入： 第第1 1行为行为n n和和m m，1n1000,1=m=100 0001n1000,1=m=100 000； 以下以下m m行，每行为行，每行为p x yp x y，p p的值为的值为0 0或或1 1，p p为为0 0时，表示时，表示x x和和y y是朋友，是朋友，p p为为1 1时，表示时，表示x x和和y y是敌人。是敌人。输出：输出： 一个整数，表示这一个整数，表示这n n个人最多可能有几个团伙。个人最多可能有几个团伙。48并查集及其应用及其应用 完完49