并查集(最终版).ppt

《并查集(最终版).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、：亲戚输入:由两部分组成：第一部分以N，M开始。N为问题涉及的人的个数。这些人的编号为1,2,3,…,N。下面有M行，每行有两个数ai,bi，表示已知ai和bi是亲戚。第二部分以Q开始。以下Q行有Q个询问，每行为ci,di，表示询问ci和di是否为亲戚。输出：对于每个询问ci,di，输出一行：若ci和di为亲戚，则输出“Yes”，否则输出“No”。请写一个程序，对于我们的关于亲戚关系的提问，以最快的速度给出答案。输入样例（relation.in）：1072457138912562333471089输出样例

3、（relation.out）：YesNoYes问题规模1：1N2551M10000001Q1000000各抒己见思路点拔题意分析算法及数据结构设计时间、空间复杂度估计及实践细节讨论优化思路讨论输入关系分离集合初始状态{1}{2}{3}{4}{5}{6}{7}{8}{9}{10}(2,4){1}{2,4}{3}{5}{6}{7}{8}{9}{10}(5,7){1}{2,4}{3}{5,7}{6}{8}{9}{10}(1,3){1,3}{2,4}{5,7}{6}{8}{9}{10}(8,9){1,

4、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}实时判断集合定义及运算：vars:setof1..100;集合与集合：交A*B、并A+B、差A-B，结果还是集合；关系运算相等=、不相等<>、包含于<=、包含>=，结果为boolean；元素与集合：xins，结果为boolean；集合的优缺点：容易理解，运算简单；数据量小、调试不

5、方便；问题规模2：1N200001M10000001Q1000000并查集并查集（union-findset）是一种用于分离集合操作的抽象数据类型。它所处理的是“集合”之间的关系，即动态地维护和处理集合元素之间复杂的关系，当给出两个元素的一个无序对(a,b)时，需要快速“合并”a和b分别所在的集合，这其间需要反复“查找”某个元素所在的集合。“并”、“查”和“集”三字由此而来。在这种数据类型中，n个不同的元素被分为若干组。每组是一个集合，这种集合叫做分离集合（disjointset）。并查集支持

6、查找一个元素所属的集合以及两个元素各自所属的集合的合并。如何用已有的数据类型或数据结构去构造？并查集本身不具有结构，必须借助一定的数据结构以得到支持和实现。数据结构的选择是一个重要的环节，选择不同的数据结构可能会在查找和合并的操作效率上有很大的差别，但操作实现都比较简单高效。并查集的数据结构实现方法很多，一般用的比较多的是，数组实现、链表实现和树实现。并查集并查集的数据结构记录了一组分离的动态集合S，S={S1,S2,…,Sk}，每个集合通过一个“代表”加以识别，代表即该集合中的某个元素（成员），哪一个成

7、员被选做代表是无所谓的，重要的是：如果求某一动态集合的代表两次，且在两次请求间不修改此集合，则两次得到的答案应该是相同的。动态集合中的每一元素是由一个对象来表示的，设x表示一个对象，并查集的实现需要支持如下操作：并查集的基本操作①MAKE-SET（x）建立一个新的集合，其仅有的成员（同时就是代表）是x。由于各集合是分离的，所以要求x没有在其它集合中出现过。②UNION（x,y）将包含x和y的动态集合（例如Sx和Sy）合并为一个新的集合，假定在此操作前这两个集合是分离的。结果的集合代表是Sx∪Sy的某个成员

8、。一般来说，在不同的实现中通常都以Sx或者Sy的代表作为新集合的代表。此后，由新的集合S代替了原来的Sx和Sy。③FIND-SET（x）返回一个包含x的集合的代表。并查集的数组实现输入样例：1072457138912562333471089UNION（x,y）过程演示：12345678910S1234567891011115558810S12345678910用数组s[i]记录元素i所属集合的编号。MAKE-SET（x）：初始