PASCAL并查集及其应用

《PASCAL并查集及其应用》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、并查集及其应用一、引例例一、亲戚(relation,pas,relation,c,relation.cpp)问题描述：或许你并不知道，你的某个朋友是你的亲戚。他可能是你的曾祖父的外公的女婿的外甥女的表姐的孙子。如果能得到完整的家谱，判断两个人是否亲戚应该是可行的，但如果两个人的最近公共祖先与他们相隔好几代，使得家谱十分庞大，那么检验亲戚关系实非人力所能及。在这种情况下，最好的帮手就是计算机。为了将问题简化，你将得到一些亲戚关系的信息，如kirry和Tom是亲戚，Tom和Ben是亲戚，等等。从这些

2、信息中，你可以推111Marry和Ben是亲戚。请写一个程序，对于我们的关于亲戚关系的提问，以最快的速度给出答案。输入输出格式：输入由两部分组成。第一部分以N,M开始。N为问题涉及的人的个数(1

3、输出“No”。输入输出样例：relation,in10724571389125623334710relation,outYesNoYes问题分析：将每个人抽象成为一个点，数据给出M个边的关系，两个人是亲戚的时候两点间有一条边。很自然的就得到了一个N个顶点M条边的图论模型，注意到传递关系，在图中一个连通块屮的任意点Z间都是亲戚。对于最后的Q个提问，即判断所提问的两个顶点是否在同一个连通块中。用传统的思路，可以马上反应过来，对于输入的N个点M条边，找出连通块，然后进行判断。但这种实现思路首先必须保存M

4、条边，然后再进行普通的遍历算法，效率显然不高。再进一步考虑，如果把题目的要求改一改，对于边和提问相间输入，即把题目改成：第一行是N,MoN为问题涉及的人的个数(1SNV20000)。这些人的编号为1,2,3,-,No下面有M行(1

5、需要在任何时候回答提问的两个人的关系，并且对于信息提示述要能立即合并两个连通块。采用连通图思想显然在实现上就有所困难，因为要表示人与人Z间的关系。用集合的思路，对于每个人建立一个集合，开始的时候集合元素是这个人本身，表示开始时不知道任何人是他的亲戚。以后每次给出一个亲戚关系时，就将两个集合合并。这样实时地得到了在当前状态下的集合关系。如果有提问，即在当前得到的结果中看两元素是否属于同一集合。对于样例数据的解释如下图1：输入关系分离集合初始状态⑴⑵⑶⑷⑸⑹｛7｝⑻⑼｛10｝(2,4){1}{2,4}

6、⑶⑸⑹{7}{8}⑼{10}(5,7){1}{2,4}⑶{5,7}{6}{8}{9}{10}(1,3){1,3}{2,4}{5,7}{6}{8}{9}{10}(&9){1,3}{2,4}{5,7}{6}{8,9}{10}(1,2){1,2,3,4}{5,7}{6}{8,9}{10}(5,6){1,2,3,4}{5,6,7}{8,9){10}(2,3)(1,2,3,4)(5,6,7}{8,9}{10}图1由图1可以看出，操作是在集合的基础上进行的，没有必要保存所有的边，而且每一步得到的划分方式是动态

7、的。那么，如何來实现以上的算法思想呢？我们就用到并查集。二、并查集的基本思想1、什么叫并查集并查集(union-findset)是一种用于分离集合操作的抽象数据类型。它所处理的是“集合”之间的关系，即动态地维护和处理集合元素之间复杂的关系，当给出两个元素的一个无序对(a,b)时，需要快速“合并”a和b分别所在的集合，这其间需要反复“查找”某元素所在的集合。“并”、“查”和“集”三字由此而来。在这种数据类型中，n个不同的元素被分为若干组。每组是一个集合，这种集合叫做分离集合(disjointset)

8、o并查集支持查找一个元素所属的集合以及两个元素各自所属的集合的合并。例如，有这样的问题：初始时n个元素分属不同的n个集合，通过不断的给出元素间的联系，要求实时的统计元素间的关系(是否存在直接或间接的联系)。这时就有了并查集的用武之地了。元素间是否有联系，只要判断两个元素是否属于同一个集合；而给出元素间的联系，建立这种联系，则只需合并两个元素各自所属的集合。这些操作都是并查集所提供的。并查集本身不具有结构，必须借助一定的数据结构以得到支持和实现。数据结构的选择是一个重要的环节，选择不