并查集及其应用

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

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

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 000 000) 1 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 000 000) 1 000 000)，每行为，每行为c ci i, , d di i，表示询问，表

4、示询问c ci i和和d di i是否为亲戚。是否为亲戚。 输出：输出： 对于每个询问对于每个询问c ci i, d, di i，输出一行：若，输出一行：若c ci i和和d di i为亲戚，则输出为亲戚，则输出“Yes”Yes”，否则输出否则输出“No”No”。 并查集及其应用及其应用 输入样例（输入样例（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）：）：YesYesNo

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

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

7、 N 20000) 20000)。这些人的编号为这些人的编号为1,2,3,1,2,3, , N 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。 这个问题比原问题更复杂些，需要在任何时候回答提问的两这个问题比原问题更复杂些，需要在任何时候回答提问的两个人的关系，并且对于信息提示还要能立即合并两个连通块。采个人的关系，并且对于信息提示还要能立即合并两个连通块。采用连通图思想显然在实现上就有所困难，因为要实时地表示人与用连通图思想显然在实现上就有所困难，因为要实时地表示人与人之间的关系。人之间的关系。 并查集及其应用及其应用 用集合的思路，对于每个人建立一个集合，开始的时候集合用集合的思路，对于每个人建立一个

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

10、2,435678910(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,910并查集及其应用及其应用 用集合

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

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

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

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

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

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

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

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

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

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

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

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

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

25、 现在讨论现在讨论UNION(x,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-S

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

27、，比如出现输入为： （2 2，1 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)。 并查集及其应用及其应用 三、并查集的实现及优化三、并查集的实现及优化 2 2、并查集的、并查集的链表链表实现实现 （2 2）快速实现）快速实现 上述简单实现非常不理想，针对上述简单实现非常不理想，针对y y可能比较大的这个问题，可可能比较大的这个问题，可以很快产生一个聪明的想

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

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

30、，当x x的代表指针（的代表指针（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次。这就保证了整个算法的复杂度是理想的。次。这就保证了整个算法的复杂度是理想的。 并查集及其应用及其应用 三、并查集的实现及优化三、并查集的实现及优化 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 th

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

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

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

35、现及优化三、并查集的实现及优化 3 3、并查集的树实现、并查集的树实现 这种树结构也可以简单地用静态数组实现，设这种树结构也可以简单地用静态数组实现，设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开始，经过一条可能比较长的路径，才能找到开始，经过一条可能比较长的路径，才能找到树根。具体实现如下：树根。具体实现如下： 并查集及其应用及其应用 三、并查集的实现及优化三、并查集的实现及优化 3 3、并查集的树实现、并查集的树实现 (1)(1)查找一个元素所属的集合查找一个元素所属的集合 在分

37、离集合森林中，每一棵分离集合树对应一个集合。要查找某一元素在分离集合森林中，每一棵分离集合树对应一个集合。要查找某一元素所属的集合，就是要找这个元素对应的结点所在的分离集合树。所属的集合，就是要找这个元素对应的结点所在的分离集合树。 不妨以分离集合树的根结点的编号来表示这个分离集合树。这样，查找不妨以分离集合树的根结点的编号来表示这个分离集合树。这样，查找一个结点所在的分离集合树，也就是查找该结点所在分离集合树的根结点了。一个结点所在的分离集合树，也就是查找该结点所在分离集合树的根结点了。 查找树的根结点的方法很简单，只需任取树中一结点（不妨就取我们要查找树的根结点的方法很简单，只需任取树中一

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

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

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

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

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

43、的数量级，的数量级，n n为结点个数，所以分为结点个数，所以分离集合森林查找与合并的平均时间复杂度为离集合森林查找与合并的平均时间复杂度为O(lognO(logn) )。但是，在最坏情况下，一棵树的深度可。但是，在最坏情况下，一棵树的深度可能达到能达到n n，如右图。这时的查找与合并的时间复杂，如右图。这时的查找与合并的时间复杂度都达到了度都达到了O(n)O(n)。这是我们不愿意看到的，因此必。这是我们不愿意看到的，因此必须想方设法避免出现这种情况。须想方设法避免出现这种情况。 为了提高效率，可以考虑在为了提高效率，可以考虑在UNION(x,y)UNION(x,y)和和FIND-FIND-SE

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

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

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

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

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

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

50、离集合树是用在分离集合森林中，分离集合是用分离集合树来表示的。分离集合树是用来联系集合中的元素的，只要同一集合中的元素在同一棵树上，不管它们在来联系集合中的元素的，只要同一集合中的元素在同一棵树上，不管它们在树中是如何被联系的，都满足分离集合树的要求。如树中是如何被联系的，都满足分离集合树的要求。如下下图，这两棵分离集合图，这两棵分离集合树是等价的，因为它们所包含的元素相同。显然，右边那棵树比较树是等价的，因为它们所包含的元素相同。显然，右边那棵树比较“优秀优秀”，因为它具有比较低的深度，相应的，查找与合并的时间复杂度也较低。那么，因为它具有比较低的深度，相应的，查找与合并的时间复杂度也较低。

51、那么，我们就应该使分离集合树尽量向右树的形式靠拢。我们就应该使分离集合树尽量向右树的形式靠拢。 并查集及其应用及其应用 在查找一个结点所在树的根结点的过程中，要经过一条从待查结点到根在查找一个结点所在树的根结点的过程中，要经过一条从待查结点到根结点的路径。我们不妨就让这些路径上的结点直接指向根结点，作为根结点结点的路径。我们不妨就让这些路径上的结点直接指向根结点，作为根结点的子结点。这样，这些路径上的结点仍在分离集合中，整棵树仍然满足分离的子结点。这样，这些路径上的结点仍在分离集合中，整棵树仍然满足分离集合树的要求，而路径上的结点的深度无疑降低了，这些点及其子树上的结集合树的要求，而路径上的结

52、点的深度无疑降低了，这些点及其子树上的结点的查找复杂度大大降低。如点的查找复杂度大大降低。如下下图，描述了在一棵分离集合树查找结点图，描述了在一棵分离集合树查找结点7 7的的前后所呈现出的结构。前后所呈现出的结构。 并查集及其应用及其应用 这种改变结点所指方向以降低结点深度，从而缩短查找路径长度的方法，这种改变结点所指方向以降低结点深度，从而缩短查找路径长度的方法，叫做路径压缩。实现路径压缩的最简单的方法是在查找从待查结点到根结点叫做路径压缩。实现路径压缩的最简单的方法是在查找从待查结点到根结点的路径时走两遍，第一遍找到树的根结点，第二遍改变路径上结点指向根结的路径时走两遍，第一遍找到树的根结

53、点，第二遍改变路径上结点指向根结点（使它们的父结点为根结点）。点（使它们的父结点为根结点）。 使用路径压缩大大提高了查找算法的效率。如果将带路径压缩的查找算使用路径压缩大大提高了查找算法的效率。如果将带路径压缩的查找算法与优化过的合并算法联合使用，则可以证明，法与优化过的合并算法联合使用，则可以证明，n n次查找最多需要用次查找最多需要用O(nO(n(n)(n)时间。时间。(n)(n)是单变量阿克曼函数的逆函数，它是一个增长速度是单变量阿克曼函数的逆函数，它是一个增长速度比比lognlogn慢的多但又不是常数的函数，在一般情况下慢的多但又不是常数的函数，在一般情况下(n)4(n)4，可以当作常

54、，可以当作常数看。数看。 这种方法是在这种方法是在FIND-SET(x)FIND-SET(x)过程中作一些改进。设想，从过程中作一些改进。设想，从x x到它的根，我到它的根，我们必须经过一条路径，显然这条路径上的所有的根与们必须经过一条路径，显然这条路径上的所有的根与x x的根是同一个根，那的根是同一个根，那么不妨在得到结果的同时，顺便把这条路上全部节点的根都改成么不妨在得到结果的同时，顺便把这条路上全部节点的根都改成x x的根，也的根，也就是说，对这些节点进行了分散，其结果是，下一次如果再有这条路上的点就是说，对这些节点进行了分散，其结果是，下一次如果再有这条路上的点进行进行FIND-SET

55、(x)FIND-SET(x)时，只要经过一步就可以找到根。可以认为是时，只要经过一步就可以找到根。可以认为是x x顺便帮了帮顺便帮了帮大家的忙，把好处带给了大家，因此其它节点以后都省事了。大家的忙，把好处带给了大家，因此其它节点以后都省事了。 并查集及其应用及其应用 r x 1 2 1 r 2 x FIND-SET(x) FIND-SET(x) 并查集及其应用及其应用 使用这两种方法优化后的代码：使用这两种方法优化后的代码： MAKE-SET(x)MAKE-SET(x) px:=x px:=x；rankx:=0rankx:=0； UNION(x,y) UNION(x,y) x:= FIND-S

56、ET(x) x:= FIND-SET(x)；y:= FIND-SET(Y)y:= FIND-SET(Y)； if rankx ranky then py:= xif rankx 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)； retu

57、rn pxreturn px； 并查集及其应用及其应用 可以看到可以看到FIND-SET(x)FIND-SET(x)是一个递归的过程。它的实现非是一个递归的过程。它的实现非常简洁，同时我们的方法也可以保证递归深度不会很深。常简洁，同时我们的方法也可以保证递归深度不会很深。 事实上只要使用这两种方法中的任何一种，算法的效事实上只要使用这两种方法中的任何一种，算法的效率都会大大提高。当两种方法结合起来以后，效率更高，率都会大大提高。当两种方法结合起来以后，效率更高，几乎可以接近几乎可以接近n n的线性复杂度。的线性复杂度。 四、引例的实现程序四、引例的实现程序1 1、数组实现、数组实现( (rel

58、ation1.pas) relation1.pas) 2 2、链表实现链表实现( (relation2.pas)relation2.pas) 3 3、树实现树实现( (relation3.pas)relation3.pas) 并查集及其应用及其应用 五、应用举例五、应用举例 并查集可以作为一些复杂问题的一部分，甚至有一些特殊的应用。这里只并查集可以作为一些复杂问题的一部分，甚至有一些特殊的应用。这里只举一些最浅显的应用例子。举一些最浅显的应用例子。 例二、例二、 食物链（食物链（NOI2001 - eatNOI2001 - eat）问题描述：问题描述： 动物王国中有三类动物动物王国中有三类动物

59、A,B,CA,B,C，这三类动物的食物链构成了有趣的环形。，这三类动物的食物链构成了有趣的环形。A A吃吃B B， B B吃吃C C，C C吃吃A A。现有。现有N 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”，

60、表示，表示X X吃吃Y Y。 此人对此人对N N个动物，用上述两种说法，一句接一句的说出个动物，用上述两种说法，一句接一句的说出K K句话，句话，这这K K句话有的是真的，有的是假的。句话有的是真的，有的是假的。 并查集及其应用及其应用 你从头开始一句一句的读入这你从头开始一句一句的读入这K K句话。当你读到的话满足下列三条之一时，句话。当你读到的话满足下列三条之一时，这句话就是假的，否则就是真的。这句话就是假的，否则就是真的。 1 1） 当前的话与前面的某些真的话冲突；当前的话与前面的某些真的话冲突； 2 2） 当前的话中当前的话中X X或或Y Y比比N N大；大； 3 3） 当前的话表示当