并查集及其应用PPT.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,并查集,及其应用,一、引例,例一、,亲戚,(relation),问题描述：,或许你并不知道，你的某个朋友是你的亲戚。他可能是你的曾祖父的外公的女婿的外甥女的表姐的孙子！,如果能得到完整的家谱，判断两个人是否亲戚应该是可行的，但如果两个人的最近公共祖先与他们相隔好几代，使得家谱十分庞大，那么检验亲戚关系实非人力所能及。在这种情况下，最好的帮手就是计算机。为了将问题简化，你将得到一些亲戚关系的信息，如,Marry,和,Tom,是亲戚，,Tom,和,Ben,是亲戚，等等。从这些信息中，你可以推出,Marry,和,Ben,是亲戚。,请写一个程序，对于我们的关于亲戚关系的提问，以最快的速度给出答案。,1,并查集,及其应用,输入由两部分组成：,第一部分以,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,”,。,2,并查集,及其应用,输入样例（,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,3,并查集,及其应用,问题分析：,将每个人抽象成为一个点，数据给出,M,个边的关系，两个人是亲戚的时候两点间有一条边。很自然的就得到了一个,N,个顶点,M,条边的图论模型，注意到传递关系，在图中一个连通块中的任意点之间都是亲戚。对于最后的,Q,个提问，即判断所提问的两个顶点是否在同一个连通块中。,用传统的思路，马上可以反应过来，对于输入的,N,个点,M,条边，找出连通块，然后进行判断。但这种实现思路首先必须保存,M,条边，然后再进行普通的遍历算法，不管是从空间还是时间上看，效率都不高。,再进一步考虑，如果把题目的要求改一改，对于边和提问相间输入，即把题目改成：,4,并查集,及其应用,第一行是,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,。,这个问题比原问题更复杂些，需要在任何时候回答提问的两个人的关系，并且对于信息提示还要能立即合并两个连通块。采用连通图思想显然在实现上就有所困难，因为要实时地表示人与人之间的关系。,5,并查集,及其应用,用集合的思路，对于每个人建立一个集合，开始的时候集合元素是这个人本身，表示开始时不知道任何人是他的亲戚。以后每次给出一个亲戚关系时，就将两个集合合并。这样实时地得到了在当前状态下的集合关系。如果有提问，即在当前得到的结果中看两元素是否属于同一集合。对于样例数据的解释如下图：,6,并查集,及其应用,输入关系 分离集合,初始状态,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,7,并查集,及其应用,用集合的思路，对于每个人建立一个集合，开始的时候集合元素是这个人本身，表示开始时不知道任何人是他的亲戚。以后每次给出一个亲戚关系时，就将两个集合合并。这样实时地得到了在当前状态下的集合关系。如果有提问，即在当前得到的结果中看两元素是否属于同一集合。对于样例数据的解释如下图：,由上图可以看出，操作是在集合的基础上进行的，没有必要保存所有的边，而且每一步得到的划分方式是动态的。,如何来实现以上的算法思想呢？我们就用到并查集。,8,并查集,及其应用,二、并查集的基本思想,1,、什么叫并查集,并查集（,union-find set,）是一种用于分离集合操作的抽象数据类型。它所处理的是,“,集合,”,之间的关系，即动态地维护和处理集合元素之间复杂的关系，当给出两个元素的一个无序对,(a,b),时，需要快速,“,合并,”,a,和,b,分别所在的集合，这其间需要反复,“,查找,”,某元素所在的集合。,“,并,”,、,“,查,”,和,“,集,”,三字由此而来。在这种数据类型中，,n,个不同的元素被分为若干组。每组是一个集合，这种集合叫做分离集合（,disjoint set,）。并查集支持查找一个元素所属的集合以及两个元素各自所属的集合的合并。,9,并查集,及其应用,二、并查集的基本思想,例如，有这样的问题：初始时,n,个元素分属不同的,n,个集合，通过不断的给出元素间的联系，要求实时的统计元素间的关系（是否存在直接或间接的联系）。这时就有了并查集的用武之地了。元素间是否有联系，只要判断两个元素是否属于同一个集合；而给出元素间的联系，建立这种联系，则只需合并两个元素各自所属的集合。这些操作都是并查集所提供的。,并查集本身不具有结构，必须借助一定的数据结构以得到支持和实现。数据结构的选择是一个重要的环节，选择不同的数据结构可能会在查找和合并的操作效率上有很大的差别，但操作实现都比较简单高效。并查集的数据结构实现方法很多，一般用的比较多的是，数组实现、链表实现和树实现。,10,并查集,及其应用,二、并查集的基本思想,并查集的数据结构记录了一组分离的动态集合,S=S1,S2,Sk,。每个集合通过一个,“,代表,”,加以识别，代表即该元素中的某个元素，哪一个成员被选做代表是无所谓的，重要的是：如果求某一动态集合的代表两次，且在两次请求间不修改集合，则两次得到的答案应该是相同的。,动态集合中的每一元素是由一个对象来表示的，设,x,表示一个对象，并查集的实现需要支持如下操作：,2,、并查集支持的操作,11,并查集,及其应用,二、并查集的基本思想,2,、并查集支持的操作,MAKE-SET,（,x,）：建立一个新的集合，其仅有的成员（同时就是代表）是,x,。由于各集合是分离的，要求,x,没有在其它集合中出现过。,UNION,（,x,y,）：将包含,x,和,y,的动态集合（例如,Sx,和,Sy,）合并为一个新的集合，假定在此操作前这两个集合是分离的。结果的集合代表是,SxSy,的某个成员。一般来说，在不同的实现中通常都以,Sx,或者,Sy,的代表作为新集合的代表。此后，由新的集合,S,代替了原来的,Sx,和,Sy,。,FIND-SET,（,x,）：返回一个指向包含,x,的集合的代表。,12,并查集,及其应用,三、并查集的实现及优化,1,、并查集的数组实现,实现并查集的最简单的方法是用数组记录每个元素所属的集合的编号。查找元素所属的集合时，只需读出数组中记录的该元素所属集合的编号即可，时间复杂度为,O(1),。合并两元素各自所属的集合时，需要将数组中属于其中一个集合的元素所对应的数组元素值全部改为另一个集合的编号值，时间复杂度为,O(n),。由于实现简单，所以实际使用的很多。,以上的数组实现虽然很方便，但是合并的代价太大。在最坏情况下，所有集合合并成一个集合的总代价可以达到,O(n,2,),。,13,并查集,及其应用,三、并查集的实现及优化,2,、并查集的,链表,实现,我们需要用一定的数据结构来组织动态的集合，同一集合中的所有元素应该是联系在一起的。一种比较简单的想法是用链表来实现，每个集合对应一个链表，它有一个表头，每一个元素有一个指针指向表头，表明了它所属的类，另有一个指针指向它的下一个元素,同时为了方便实现，再设一个指针,last,表示链表中的最后一个元素（表尾）。可以选择静态数组（一般来说这种问题处理的对象都是连续整数，可以用下标来对应元素）来实现，定义一个记录为：,type node=record,head,next,last:integer;,end;,var S:array1.maxn of node;,14,并查集,及其应用,三、并查集的实现及优化,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,值修改，这需要线性的赋值操作，其复杂度与选择接在尾部的链表长度成正比。,15,并查集,及其应用,三、并查集的实现及优化,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),。,16,并查集,及其应用,三、并查集的实现及优化,2,、并查集的,链表,实现,（,2,）快速实现,上述简单实现非常不理想，针对,y,可能比较大的这个问题，可以很快产生一个聪明的想法：不妨比较,x,和,y,所在集合的大小，从而作出选择，把较短的链表接在较长的尾部，这样效果是一样的，但耗费肯定不比原来差。这就是快速实现的思路。可以在,node,里多设一个域,number,，用来记录此条链表中成员的个数。显然,number,记录在表头元素中即可，将两表合并的时候，只要将表的,number,相加，因此维护起来是非常方便的。,这种快速实现的方法可以称为加权启发式合并，这里的权就是指所记录的,number,。,17,并查集,及其应用,三、并查集的实现及优化,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,次。这就保证了整个算法的复杂度是理想的。,18,并查集,及其应用,三、并查集的实现及优化,2,、并查集的,链表,实现,合并两个集合时的实现过程如下：,UNION(x,y),x=FIND-SET(x);,y=FIND-SET(y);,if x.numbery.number then UNION(x,y),else UNION(y,x);,并查集的链表实现是一种非常容易接受的算法，并且它的效率也是令人满意的。其实它的思路和数组完全一样，所以实际使用较少。,19,并查集,及其应用,三、并查集的实现及优化,3,、并查集的树实现,实现并查集的另一种方法是利用树。我们用有根树来表示集合，树中的每个节点包含集合的一个成员，每棵树表示一个集合。多个集合形成森林态，以每棵树的树根作为集合的代表，并且根结点的父结点指向其自身，树上的其他结点都用一个父指针表示它的附属关系。,注意：在同一棵树中的结点属于同一个集合，虽然它们在树中存在父子结点关系，但并不意味着它们之间存在从属关系。树的指针起的只是联系集合中元素的作用。,在并查集中，每个分离集合对应的一棵树，称为分离集合树。整个并查集也就是一棵分离集合森林。,20,并查集,及其应用,三、并查集的实现及优化,3,、并查集的树实现,下图表示了这种关系，其包含两个集合,b,c,e,h,d,f,g,分别以,c,和,f,作为代表。,21,并查集,及其应用,三、并查集的实现及优化,3,、并查集的树实现,这种树结构也可以简单地用静态数组实现，设,px,表示,x,元素所指向的父亲。,MAKE-SET(x),：,px=x;,FIND-SET(x),：要从,x,开始，向上寻找它的父亲，直到找到根为止。,UNION,（,x,y,）：只要使一棵树的根指向另一棵树的根，即成为一棵子树。,可以发现，元素之间的联系是靠指针来实现的，与链表的实现相比，所,需要进行的修改少了许多。但可以发现，,UNION,（,x,y,）虽然是简便了许多，,但是,FIND-SET,（,x,）则需要从,x,开始，经过一条可能比较长的路径，才能找到,树根。具体实现如下：,22,并查集,及其应用,三、并查集的实现及优化,3,、并查集的树实现,(1),查找一个元素所属的集合,在分离集合森林中，每一棵分离集合树对应一个集合。要查找某一元素所属的集合，就是要找这个元素对应的结点所在的分离集合树。,不妨以分离集合树的根结点的编号来表示这个分离集合树。这样，查找一个结点所在的分离集合树，也就是查找该结点所在分离集合树的根结点了。,查找树的根结点的方法很简单，只需任取树中一结点（不妨就取我们要查找的那个结点），沿父结点方向一直往树根走：初始时，取一个结点，走到它的父结点，然后以父结点为基点，走到父结点的父结点,直至走到一个没有父结点的结点为止，这个结点就是树的根结点。,23,并查集,及其应用,三、并查集的实现及优化,3,、并查集的树实现,(1),查找一个元素所属的集合,下,图描述了查找一个结点的过程（黑色结点为当前查找结点）。,查找算法的复杂度取决于查找结点的深度，假设查找结点的深度为,h,，则算法的时间复杂度为,O(h),。,24,并查集,及其应用,三、并查集的实现及优化,3,、并查集的树实现,(2),两个元素各自所属的集合的合并,在分离集合森林中，分离集合是用分离集合树来表示的。要合并两个元素各自所属的集合，也就是合并两元素所对应的两个结点各自所在的分离集合树。,现在的问题就是如何合并两棵分离集合树。考虑到在分离集合森林中，只要结点属于同一棵树，即被视为在同一个集合中，而不管具体是如何相连的。那么，我们只需简单的将一棵分离集合树作为另一棵的子树，即可使两棵树合并为一棵。,如下图，描述的是将两棵分离集合树,D,1,和,D,2,合并的过程（,D,1,作为,D,2,的根结点的一棵子树）。,25,并查集,及其应用,三、并查集的实现及优化,3,、并查集的树实现,(2),两个元素各自所属的集合的合并,要完成上述合并，首先要找到两棵分离集合树的根结点，这可以通过调用两次查找算法得到。得到根结点后，只需改变其中一个根结点，令它的父结点为另一个根结点即可，代价为,O(1),。因此，整个合并算法的复杂度主要在查找根结点部分，为,O(h),。,26,并查集,及其应用,三、并查集的实现及优化,3,、并查集的树实现,(3),优化查找与合并算法,前面提到，分离集合森林的查找与合并的时间复杂度都是,O(h),。也就是说，查找与合并的时间复杂度主要取决于树的深度。就平均情况而言，树的深度应该在,logn,的数量级，,n,为结点个数，所以分离集合森林查找与合并的平均时间复杂度为,O(logn),。但是，在最坏情况下，一棵树的深度可能达到,n,，如右图。这时的查找与合并的时间复杂度都达到了,O(n),。这是我们不愿意看到的，因此必须想方设法避免出现这种情况。,为了提高效率，可以考虑在,UNION(x,y),和,FIND-SET(x),上作一些文章。,27,并查集,及其应用,三、并查集的实现及优化,3,、并查集的树实现,(3),优化查找与合并算法,优化合并过程,分析一下前面那棵深度为,n,的分离集合树的形成过程，可以看出，这是合并不当的后果。当合并右图的两棵分离集合树（,A,，,B,）时，显然将,B,树作为,A,树根结点的子树得到的树比较平衡，如下图中的,C,树（,D,树为,A,树作为,B,树根结点的子树得到的树）。,28,并查集,及其应用,三、并查集的实现及优化,3,、并查集的树实现,(3),优化查找与合并算法,优化合并过程,一棵较平衡的树拥有比较低的深度，查找和合并的复杂度也就相应得较低。因此，如果两棵分离集合树,A,和,B,，深度分别为,h,A,和,h,B,，则若,h,A,h,B,，应将,B,树作为,A,树的子树；否则，将,A,树作为,B,树的子树。总之，总是深度较小的分离集合树作为子树。得到的新的分离集合树,C,的深度,h,C,，以,B,树作,A,树的子树为例，,h,C,=maxh,A,h,B,+1,。,这样合并得到的分离集合树，其深度不会超过,logn,，是一个比较平衡的树。因此，查找与合并的时间复杂度也就稳定在,O(logn),了。,29,并查集,及其应用,三、并查集的实现及优化,3,、并查集的树实现,(3),优化查找与合并算法,优化查找过程,对于查找过程有两个方面的启发式方法都很有效，分别是按秩合并和路径压缩优化。,30,并查集,及其应用,A,按秩合并,可以联系一下链表的优化，我们是选择比较小的一个集合归并到大的集合里去。对于有根树的结构，很类似地，也可以记录树上的节点数，将较小的树的根指向较大的树。但是有根树的结构又有非常特殊的地方，它的一个节点下面可能挂有很多子树；从前面分析也可以看出，主要的时间花在了,FIND-SET,（,x,）上，只要使得树中不存在一条偏长的路径，即使得各条路径的长度都比较平均了，那么算法就不会出现特别退化的情况。对每个结点，用一个秩（,rank,）来近似子树大小对数，同时它也是该节点高度的一个上界。进行,UNION,的时候，只要让具有较小秩的根指向具有较大秩的根。如果两根的秩相等，只要使其中一个根指向另一个，同时秩应当增加,1,。这十分类似于统计节点个数，但这里统计的是树的深度。,31,并查集,及其应用,B,路径压缩优化方法,在分离集合森林中，分离集合是用分离集合树来表示的。分离集合树是用来联系集合中的元素的，只要同一集合中的元素在同一棵树上，不管它们在树中是如何被联系的，都满足分离集合树的要求。如,下,图，这两棵分离集合树是等价的，因为它们所包含的元素相同。显然，右边那棵树比较,“,优秀,”,，因为它具有比较低的深度，相应的，查找与合并的时间复杂度也较低。那么，我们就应该使分离集合树尽量向右树的形式靠拢。,32,并查集,及其应用,在查找一个结点所在树的根结点的过程中，要经过一条从待查结点到根结点的路径。我们不妨就让这些路径上的结点直接指向根结点，作为根结点的子结点。这样，这些路径上的结点仍在分离集合中，整棵树仍然满足分离集合树的要求，而路径上的结点的深度无疑降低了，这些点及其子树上的结点的查找复杂度大大降低。如,下,图，描述了在一棵分离集合树查找结点,7,的前后所呈现出的结构。,33,并查集,及其应用,这种改变结点所指方向以降低结点深度，从而缩短查找路径长度的方法，叫做路径压缩。实现路径压缩的最简单的方法是在查找从待查结点到根结点的路径时走两遍，第一遍找到树的根结点，第二遍改变路径上结点指向根结点（使它们的父结点为根结点）。,使用路径压缩大大提高了查找算法的效率。如果将带路径压缩的查找算法与优化过的合并算法联合使用，则可以证明，,n,次查找最多需要用,O(n,(n),时间。,(n),是单变量阿克曼函数的逆函数，它是一个增长速度比,logn,慢的多但又不是常数的函数，在一般情况下,(n)4,，可以当作常数看。,这种方法是在,FIND-SET(x),过程中作一些改进。设想，从,x,到它的根，我们必须经过一条路径，显然这条路径上的所有的根与,x,的根是同一个根，那么不妨在得到结果的同时，顺便把这条路上全部节点的根都改成,x,的根，也就是说，对这些节点进行了分散，其结果是，下一次如果再有这条路上的点进行,FIND-SET(x),时，只要经过一步就可以找到根。可以认为是,x,顺便帮了帮大家的忙，把好处带给了大家，因此其它节点以后都省事了。,34,并查集,及其应用,FIND-SET(x),35,并查集,及其应用,使用这两种方法优化后的代码：,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-SET(x),if xpx then px:=FIND-SET(px),；,return px,；,36,并查集,及其应用,可以看到,FIND-SET(x),是一个递归的过程。它的实现非常简洁，同时我们的方法也可以保证递归深度不会很深。,事实上只要使用这两种方法中的任何一种，算法的效率都会大大提高。当两种方法结合起来以后，效率更高，几乎可以接近,n,的线性复杂度。,四、引例的实现程序,1,、数组实现,(relation1.pas),2,、,链表实现,(relation2.pas),3,、,树实现,(relation3.pas),37,并查集,及其应用,五、应用举例,并查集可以作为一些复杂问题的一部分，甚至有一些特殊的应用。这里只举一些最浅显的应用例子。,例二、,食物链（,NOI2001-eat,）,问题描述：,动物王国中有三类动物,A,B,C,，这三类动物的食物链构成了有趣的环形。,A,吃,B,，,B,吃,C,，,C,吃,A,。现有,N,个动物，以,1,N,编号。每个动物都是,A,B,C,中的一种，但是我们并不知道它到底是哪一种。有人用两种说法对这,N,个动物所构成的食物链关系进行描述：,第一种说法是,“,1 X Y,”,，表示,X,和,Y,是同类。,第二种说法是,“,2 X Y,”,，表示,X,吃,Y,。,此人对,N,个动物，用上述两种说法，一句接一句的说出,K,句话，,这,K,句话有的是真的，有的是假的。,38,并查集,及其应用,你从头开始一句一句的读入这,K,句话。当你读到的话满足下列三条之一时，这句话就是假的，否则就是真的。,1,）,当前的话与前面的某些真的话冲突；,2,）,当前的话中,X,或,Y,比,N,大；,3,）,当前的话表示,X,吃,X,。,你的任务是根据给定的,N,（,1=N=50,000,）和,K,个条件（,0=K=100,000,），输出假话的总数。,输入文件（,eat.in,）：,第一行是两个整数,N,和,K,，以一个空格分隔。,以下,K,行每行是三个正整数,D,，,X,，,Y,，之间用一个空格隔开，其中,D,表示说法的种类。若,D=1,，,X,和,Y,是同类。若,D=2,，,X,吃,Y,。,输出文件（,eat.out,）：,一个整数，表示假话的数目。,39,并查集,及其应用,输入样例：,100 7,1 101 1 /,假,2 1 2 /,真,2 2 3 /,真,2 3 3 /,假,1 1 3 /,假,2 3 1 /,真,1 5 5 /,真,输出样例,:,3,40,并查集,及其应用,算法分析：,本题和亲戚问题其实是差不多的，两者的数学模型已经不能再相似了。它就相当于例一中提出的亲戚问题的第,2,版，即边合并还需要边判断。本题的难点恐怕在于两个点的关系不仅是同集合的关系，还涉及到在同一集合中处于怎样的捕食关系，显然在同一个集合中还需要对各种动物进行标号。用,0,，,1,，,2,对每种动物染色，如下图所示：,如果两个动物,x,和,y,同类，,则,colorx=colory;,如果,x,吃,y,，,那么,(colorx+1)mod 3=colory,。,41,并查集,及其应用,这时对两个集合,UNION,（,x,y,）进行合并时就需要做更多的工作。假定,x,集合颜色不变，那么要把,y,集合并到,x,集合中，,y,集合的每个元素只要全部相应增加某一个增值,d,，就可以把,x,，,y,统一起来了。例如,x,和,y,属于同类，而,colorx=2,，,colory=1,，,y,集合中所有元素的颜色都增加,1,（,mod 3,），两集合元素的颜色就统一了。,考虑该算法的实现。前面的讨论中，可知用有根树来实现效率是非常高的，但高效的方法未必好用，比如对于此题，如果采用有根树的直接实现，由于元素之间存在染色的转换，那么维护有根树时，树内动物之间的关系无法及时明确。事实上本题可以简单地采用链表实现的方法，前面已经说了，只要将,y,里面的元素进行一下调整，链表实现中本来就需要对,y,集合里每个节点的代表指针进行调整，因此此步改变只需要在原算法中稍作添加，不需要更进一步的复杂讨论了。,42,并查集,及其应用,例三、求无向图的连通分量,这个问题其实在例一中已经提过了。这里再单独提出来强调一下，因为求无向图连通分量是个非常常用的算法。通过并查集可以使得空间上省去对边的保存，同时时间效率又是很高的。,需要特别指出的是，如果用链表来实现的话，最后任何在同一个集合（即连通块）中的元素，其代表指针的值都是相等的。而采用有根树来实现的话，算法结束后，留下的依然是树的关系，因此如果希望每个元素都指向它的根的话，还需要对每个节点进行一次,FIND-SET,操作，这样每个节点的父节点都是代表此集合的节点。在某些统计问题中，往往需要这样做。而从另一方面讲，有根树的实现，如果忽略,“,按秩合并,”,这一优化，时间效率依然是很高的，但可以省去,RANK,这个线性空间的保存。因此在某些时候如果内存紧张的话，是可以以牺牲时间来换取空间的。,43,并查集,及其应用,例四、,Kruskal,最小生成树算法,此经典算法的思想是将树上的边按照权排序，然后从小到大分析每一条边，如果选到一条边,e=(v1,v2),且,v1,和,v2,不在一个连通块中，就将,e,作为最小生成树的一条边，否则忽略,e,。这其中明显就包含了并查集的算法。,Kruskal,算法也只有在结合了并查集后才能说是个有效的算法。,44,并查集,及其应用,六、小结,并查集的三种实现都是简单而高效的。对于某些具体的问题，到底用怎样的实现，是需要进一步推敲的。不管怎么说它只是一种底层的数据结构，它的实现应该和具体问题的特征结合在一起。,另外考察并查集的分析方法：首先我们提出用集合来实现元素之间关系，然后，我们考察它需要支持的操作，接着是具体的实现，对于不同的实现，又有针对性地进行优化。设想,分析,优化,推广,这是分析数据结构一般的方法。另一方面，并查集的优化主要依靠启发式，这一点在思考问题的时候也是常用的，实际上就是这点简单的启发，将随意的过程有意化，大幅度地提高了效率，避免了性能上的退化。,45,并查集,及其应用,七、作业,作业,1,、家谱,(GEN,时间限制,:2S),问题描述,:,现代的人对于本家族血统越来越感兴趣，现在给出充足的父子关系，请你编写,程序找到某个人的最早的祖先。,输入,:,输入文件由多行组成，首先是一系列有关父子关系的描述，其中每一组父子关系,由二行组成，用,#name,的形式描写一组父子关系中的父亲的名字，用,+name,的形式描写,一组父子关系中的儿子的名字；接下来用,?name,的形式表示要求该人的最早的祖先；,最后用单独的一个,$,表示文件结束。,规定每个人的名字都有且只有,6,个字符，而且首字母大写，且没有任意两个人的名,字相同。最多可能有,1000,组父子关系，总人数最多可能达到,50000,人，家谱中的记载不,超过,30,代。,输出,:,按照输入文件的要求顺序，求出每一个要找祖先的人的祖先，,格式：本人的名字,+,一个空格,+,祖先的名字,+,回车。,46,并查集,及其应用,样例输入：,GEN.IN,#George,+Rodney,#Arthur,+Gareth,+Walter,#Gareth,+Edward,?Edward,?Walter,?Rodney,?Arthur,$,样例输出：,GEN.OUT,Edward Arthur,Walter Arthur,Rodney George,Arthur Arthur,47,并查集,及其应用,作业,2,、团伙,(group,，时间限制：,2S),问题描述：,在某城市里住着,n,个人，任何两个认识的人不是朋友就是敌人，而且满足：,1,、,我朋友的朋友是我的朋友；,2,、,我敌人的敌人是我的朋友；,所有是朋友的人组成一个团伙。告诉你关于这,n,个人的,m,条信息，即某两个人是,朋友，或者某两个人是敌人，请你编写一个程序，计算出这个城市最多可能有多少,个团伙？,输入：,第,1,行为,n,和,m,，,1n1000,1=m=100 000,；,以下,m,行，每行为,p x y,，,p,的值为,0,或,1,，,p,为,0,时，表示,x,和,y,是朋友，,p,为,1,时，表示,x,和,y,是敌人。,输出：,一个整数，表示这,n,个人最多可能有几个团伙。,48,并查集,及其应用,完,49,