并查集及其应用

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,并查集,及其应用,一、引例,例一、,亲戚(,relation),问题描述：,或许你并不知道，你的某个朋友是你的亲戚。他可能是你的曾祖父的外公的女婿的外甥女的表姐的孙子！,如果能得到完整的家谱，判断两个人是否亲戚应该是可行的，但如果两个人的最近公共祖先与他们相隔好几代，使得家谱十分庞大，那么检验亲戚关系实非人力所能及。在这种情况下，最好的帮手就是计算机。为了将问题简化，你将得到一些亲戚关系的信息，如,Marry,和,Tom,是亲戚，,Tom,和,Ben,是亲戚，等等。从这些信息中，你可以推出,Marry,和,Ben,是亲戚。,请写一个程序，对于我们的关于亲戚关系的提问，以最快的速度给出答案。,并查集,及其应用,输入由两部分组成：,第一部分以,N，M,开始。,N,为问题涉及的人的个数(1,N,20000)。,这些人的编号为1,2,3,N。,下面有,M,行(1,M,1 000 000)，,每行有两个数,a,i,b,i,，,表示已知,a,i,和,b,i,是亲戚。,第二部分以,Q,开始。以下,Q,行有,Q,个询问(1,Q,1 000 000)，,每行为,c,i,d,i,，,表示询问,c,i,和,d,i,是否为亲戚。,输出：,对于每个询问,c,i,d,i,，,输出一行：若,c,i,和,d,i,为亲戚，则输出“,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,并查集,及其应用,问题分析：,将每个人抽象成为一个点，数据给出,M,个边的关系，两个人是亲戚的时候两点间有一条边。很自然的就得到了一个,N,个顶点,M,条边的图论模型，注意到传递关系，在图中一个连通块中的任意点之间都是亲戚。对于最后的,Q,个提问，即判断所提问的两个顶点是否在同一个连通块中。,用传统的思路，马上可以反应过来，对于输入的,N,个点,M,条边，找出连通块，然后进行判断。但这种实现思路首先必须保存,M,条边，然后再进行普通的遍历算法，不管是从空间还是时间上看，效率都不高。,再进一步考虑，如果把题目的要求改一改，对于边和提问相间输入，即把题目改成：,并查集,及其应用,第一行是,N，M。N,为问题涉及的人的个数(1,N,20000)。,这些人的编号为1,2,3,N。,下面有,M,行(1,M,2 000 000)，,每行有三个数,k,i,a,i,b,i,a,i,和,b,i,表示两个元素，,k,i,为0或1，,k,i,为1时表示这是一条边的信息，即,a,表示,i,和,b,i,是亲戚关系；,k,i,为0时表示这是一个提问，要你根据此行以前所得到的信息，判断,a,i,和,b,i,是否是亲戚，对于每条提问回答,Yes,或者,No。,这个问题比原问题更复杂些，需要在任何时候回答提问的两个人的关系，并且对于信息提示还要能立即合并两个连通块。采用连通图思想显然在实现上就有所困难，因为要实时地表示人与人之间的关系。,并查集,及其应用,用集合的思路，对于每个人建立一个集合，开始的时候集合元素是这个人本身，表示开始时不知道任何人是他的亲戚。以后每次给出一个亲戚关系时，就将两个集合合并。这样实时地得到了在当前状态下的集合关系。如果有提问，即在当前得到的结果中看两元素是否属于同一集合。对于样例数据的解释如下图：,并查集,及其应用,输入关系 分离集合,初始状态 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,并查集,及其应用,用集合的思路，对于每个人建立一个集合，开始的时候集合元素是这个人本身，表示开始时不知道任何人是他的亲戚。以后每次给出一个亲戚关系时，就将两个集合合并。这样实时地得到了在当前状态下的集合关系。如果有提问，即在当前得到的结果中看两元素是否属于同一集合。对于样例数据的解释如下图：,由上图可以看出，操作是在集合的基础上进行的，没有必要保存所有的边，而且每一步得到的划分方式是动态的。,如何来实现以上的算法思想呢？我们就用到并查集。,并查集,及其应用,二、并查集的基本思想,1、什么叫并查集,并查集（,union-find set）,是一种用于分离集合操作的抽象数据类型。它所处理的是“集合”之间的关系，即动态地维护和处理集合元素之间复杂的关系，当给出两个元素的一个无序对(,a,b),时，需要快速“合并”,a,和,b,分别所在的集合，这其间需要反复“查找”某元素所在的集合。“并”、“查”和“集”三字由此而来。在这种数据类型中，,n,个不同的元素被分为若干组。每组是一个集合，这种集合叫做分离集合（,disjoint set）。,并查集支持查找一个元素所属的集合以及两个元素各自所属的集合的合并。,并查集,及其应用,二、并查集的基本思想,例如，有这样的问题：初始时,n,个元素分属不同的,n,个集合，通过不断的给出元素间的联系，要求实时的统计元素间的关系（是否存在直接或间接的联系）。这时就有了并查集的用武之地了。元素间是否有联系，只要判断两个元素是否属于同一个集合；而给出元素间的联系，建立这种联系，则只需合并两个元素各自所属的集合。这些操作都是并查集所提供的。,并查集本身不具有结构，必须借助一定的数据结构以得到支持和实现。数据结构的选择是一个重要的环节，选择不同的数据结构可能会在查找和合并的操作效率上有很大的差别，但操作实现都比较简单高效。并查集的数据结构实现方法很多，一般用的比较多的是，数组实现、链表实现和树实现。,并查集,及其应用,二、并查集的基本思想,并查集的数据结构记录了一组分离的动态集合,S=S1,S2,Sk,。,每个集合通过一个“代表”加以识别，代表即该元素中的某个元素，哪一个成员被选做代表是无所谓的，重要的是：如果求某一动态集合的代表两次，且在两次请求间不修改集合，则两次得到的答案应该是相同的。,动态集合中的每一元素是由一个对象来表示的，设,x,表示一个对象，并查集的实现需要支持如下操作：,2、并查集支持的操作,并查集,及其应用,二、并查集的基本思想,2、并查集支持的操作,MAKE-SET（x）：,建立一个新的集合，其仅有的成员（同时就是代表）是,x。,由于各集合是分离的，要求,x,没有在其它集合中出现过。,UNION（x,y）：,将包含,x,和,y,的动态集合（例如,Sx,和,Sy,）,合并为一个新的集合，假定在此操作前这两个集合是分离的。结果的集合代表是,Sx,Sy,的某个成员。一般来说，在不同的实现中通常都以,Sx,或者,Sy,的代表作为新集合的代表。此后，由新的集合,S,代替了原来的,Sx,和,Sy,。,FIND-SET（x）：,返回一个指向包含,x,的集合的代表。,并查集,及其应用,三、并查集的实现及优化,1、并查集的数组实现,实现并查集的最简单的方法是用数组记录每个元素所属的集合的编号。查找元素所属的集合时，只需读出数组中记录的该元素所属集合的编号即可，时间复杂度为,O(1)。,合并两元素各自所属的集合时，需要将数组中属于其中一个集合的元素所对应的数组元素值全部改为另一个集合的编号值，时间复杂度为,O(n)。,由于实现简单，所以实际使用的很多。,以上的数组实现虽然很方便，但是合并的代价太大。在最坏情况下，所有集合合并成一个集合的总代价可以达到,O(n,2,)。,并查集,及其应用,三、并查集的实现及优化,2、并查集的,链表,实现,我们需要用一定的数据结构来组织动态的集合，同一集合中的所有元素应该是联系在一起的。一种比较简单的想法是用链表来实现，每个集合对应一个链表，它有一个表头，每一个元素有一个指针指向表头，表明了它所属的类，另有一个指针指向它的下一个元素,同时为了方便实现，再设一个指针,last,表示链表中的最后一个元素（表尾）。可以选择静态数组（一般来说这种问题处理的对象都是连续整数，可以用下标来对应元素）来实现，定义一个记录为：,type node=record,head,next,last:integer;,end;,var,S:array1.,maxn,of node;,并查集,及其应用,三、并查集的实现及优化,2、并查集的,链表,实现,可以得到,MAKE-SET,和,FIND-SET,的实现为：,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,值修改，这需要线性的赋值操作，其复杂度与选择接在尾部的链表长度成正比。,并查集,及其应用,三、并查集的实现及优化,2、并查集的,链表,实现,现在讨论,UNION(x,y),的实现，假设,UNION(x,y),的参数是有序的，即把,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,1),显然,y,所在的集合越来越庞大，对于这种方法最坏情况下时间复杂度为,O(n2)。,并查集,及其应用,三、并查集的实现及优化,2、并查集的,链表,实现,（2）快速实现,上述简单实现非常不理想，针对,y,可能比较大的这个问题，可以很快产生一个聪明的想法：不妨比较,x,和,y,所在集合的大小，从而作出选择，把较短的链表接在较长的尾部，这样效果是一样的，但耗费肯定不比原来差。这就是快速实现的思路。可以在,node,里多设一个域,number，,用来记录此条链表中成员的个数。显然,number,记录在表头元素中即可，将两表合并的时候，只要将表的,number,相加，因此维护起来是非常方便的。,这种快速实现的方法可以称为加权启发式合并，这里的权就是指所记录的,number。,并查集,及其应用,三、并查集的实现及优化,2、并查集的,链表,实现,可以证明这种方法的效率。当有,n,个元素时，在,UNION,上的花费（即重新赋值的次数）的上界是,O(nlog,2,n)。,考虑一个固定的对象,x，,当,x,的代表指针（,head）,被更新时，,x,必是属于一个较小的集合，因此，,x,的代表指针第一次更新后，结果集合必然至少有2个元素，类似的，下一次更新后，,x,所在的集合至少有4个元素。继续下去，可以发现，,x,的代表指针最多被更新,log,2,n,次，因为当,x,所在集合元素已经等于,n,以后，不可能再发生,UNION,操作。所以，总共有,n,个元素时，操作的总次数不超过,nlog,2,n,次。这就保证了整个算法的复杂度是理想的。,并查集,及其应用,三、并查集的实现及优化,2、并查集的,链表,实现,合并两个集合时的实现过程如下：,UNION(x,y),x=