资源描述：
《ACMICPC重要补充知识.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、在一些有N个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。这一类问题近几年来反复出现在信息学的国际国内赛题中，其特点是看似并不复杂，但数据量极大，若用正常的数据结构来描述的话，往往在空间上过大，计算机无法承受；即使在空间上勉强通过，运行的时间复杂度也极高，根本就不可能在比赛规定的运行时间（1～3秒）内计算出试题需要的结果，只能采用一种全新的抽象的特殊数据结构——并查集来描述。什么是并查集？ 并查集是一种树型的数据结构，用于处理一些不相交集合（Disj
2、ointSets）的合并及查询问题。常常在使用中以森林来表示。 集就是让每个元素构成一个单元素的集合，并就是按一定顺序将属于同一组的元素所在的集合合并。编辑本段并查集的主要操作：初始化 把每个点所在集合初始化为其自身查找 查找元素所在的集合即根节点合并 将两个元素所在的集合合并为一个集合 合并两个不相交集合判断两个元素是否属于同一集合辅助例题 亲戚(Relations) 题目描述：若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，现在给出某个亲戚关系图，求任意给出的两个人是否具有亲戚关系。 规定：x和y是亲戚，y和z是亲戚，那么x和
3、z也是亲戚。如果x,y是亲戚，那么x的亲戚都是y的亲戚，y的亲戚也都是x的亲戚。输入格式InputFormat第一行：三个整数n,m,p，（n<=5000,m<=5000,p<=5000），分别表示有n个人，m个亲戚关系，询问p对亲戚关系。以下m行：每行两个数Mi，Mj，1<=Mi，Mj<=N，表示Ai和Bi具有亲戚关系。接下来p行：每行两个数Pi，Pj，询问Pi和Pj是否具有亲戚关系。输出格式OutputFormatP行，每行一个’Yes’或’No’。表示第i个询问的答案为“具有”或“不具有”亲戚关系。 var father:array[1..5000]
4、ofinteger; i,j,k,p,n,m:integer; Functiongetfather(v:integer):integer; begin iffather[v]=vthenexit(v); father[v]:=getfather(father[v]); getfather:=father[v]; end; Proceduremerge(x,y:integer); begin x:=getfather(x); y:=getfather(y); father[x]:=y; end; Functionjudge(x,y:i
5、nteger):boolean; begin x:=getfather(x); y:=getfather(y); Ifx=ythenexit(true)elseexit(false); end; begin readln(n,m,p); fori:=1tondofather[i]:=i;{预处理} fori:=1tomdo begin read(j,k); merge(j,k); end; fori:=1topdo begin read(j,k); ifjudge(j,k)thenwriteln('Yes')elsewrite
6、ln('No'); end; end.编辑本段思路点拨一问题实质 初步分析觉得本题是一个图论中判断两个点是否在同一个连通子图中的问题。对于题目中的样例，以人为点，关系为边，建立无向图如下： 图0-0-1{请补充图解} 比如判断3和4是否为亲戚时，我们检查3和4是否在同一个连通子图中，结果是，于是他们是亲戚。又如7和10不在同一个连通子图中，所以他们不是亲戚。 用图的数据结构的最大问题是，我们无法存下多至(M=)2000000条边的图，后面关于算法时效等诸多问题就免谈了。 用图表示关系过于“奢侈”了。其实本题只是一个对分离集合（并查集）操作的问题。
7、 我们可以给每个人建立一个集合，集合的元素值有他自己，表示最开始时他不知道任何人是它的亲戚。以后每次给出一个亲戚关系a,b，则a和他的亲戚与b和他的亲戚就互为亲戚了，将a所在集合与b所在集合合并。对于样例数据的操作全过程如下： 输入关系分离集合 初始状态 (2,4){2,4} (5,7){2,4}{5,7} (1,3){1,3}{2,4}{5,7} (8,9){1,3}{2,4}{5,7}{8,9} (1,2){1,2,3,4}{5,7}{8,9} (5,6){1,2,3,4}{5,6,7}{8,9} (2,3){1,2,3,4}{5,6,
8、7}{8,9} 最后我们得到4个集合
