信息学奥赛

《信息学奥赛》由会员分享，可在线阅读，更多相关《信息学奥赛（7页珍藏版）》请在金锄头文库上搜索。

1、在一些有N个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素 的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在 哪个集合中。这一类问题近几年来反复出现在信息学的国际国内赛题中，其特点是看似并不 复杂，但数据量极大，若用正常的数据结构来描述的话，往往在空间上过大，计算机无法承 受；即使在空间上勉强通过，运行的时间复杂度也极高，根本就不可能在比赛规定的运行时 间（13秒）内计算出试题需要的结果，只能采用一种全新的抽象的特殊数据结构一一并查 集来描述。一、数学准备首先，我们从数学的角度给出等价关系和等价类的定义：定义1：如果集合S中的关系R是自反的，对

2、称的，传递的，则称他为一个等价关系。自反：x = x；对称：若x = y，贝i y = x；传递：若 x = y、y = z，贝i x = zo要求：x、y、z必须要同一个子集中。定义2：如果R是集合S的等价关系。对于任何xS，由xR=y|yWS and xRy给出 的集合xR S称为由xES生成的一个R的等价类。定义3：若R是集合S上的一个等价关系，则由这个等价关系可产生这个集合的唯一划 分。即可以按R将S划分为若干不相交的子集S, S,S,S,，他们的并即为S，则这1234些子集S变称为S的R等价类。i划分等价类的问题的提法是：要求对S作出符合某些等价性条件的等价类的划分，已知 集合S及一

3、系列的形如“x等价于y”的具体条件，要求给出S的等价类的划分，符合所列等 价性的条件。（我们上面提到的联系，即可认为是一个等价关系，我们就是要将集合S划分成 n个联系的子集，然后再判断x, y是否在一个联系子集中。）二、弓I题亲戚（relation）【问题描述】若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，现 在给出某个亲戚关系图，求任意给出的两个人是否具有亲戚关系。规定：X和y是亲戚，y和z是亲戚，那么X和z也是亲戚。如果x, y是亲戚，那么x的 亲戚都是y的亲戚，y的亲戚也都是x的亲戚。（人数5000，亲戚关系5000，询问亲戚关 系次数5000）。【算法分析】1. 算法1

4、，构造图论模型。用一个 n*n 的二维数组描述上面的图形，记忆各个点之间的关系。然后，只要判断给定 的两个点是否连通则可知两个元素是否有“亲戚”关系。但要实现上述算法，我们遇到两个困难：(1) 空间问题：需要n2的空间，而n高达5000!(2) 时间问题：每次判断连通性需要O(n)的处理。该算法显然不理想。 并查集多用于图论问题的处理优化，我们看看并查集在这里的表现如何。2. 算法 2，并查集的简单处理。 我们把一个连通块看作一个集合，问题就转化为判断两个元素是否属于同一个集合。假设一开始每个元素各自属于自己的一个集合，每次往图中加一条边a b,就相当于合 并了两个元素所在集合A和B因为集合A

5、中的元素用过边ab可以到达集合B中的任意元 素，反之亦然。当然如果a和b本来就已经属于同一个集合了，那么a-b这条边就可以不用加了。(1) 具体操作： 由此用某个元素所在树的根结点表示该元素所在的集合； 判断两个元素时候属于同一个集合的时候，只需要判断他们所在树的根结点是否一样 即可； 也就是说，当我们合并两个集合的时候，只需要在两个根结点之间连边即可。(2) 元素的合并图示：(3) 判断元素是否属于同一集合：用fatheri表示元素i的父亲结点，如刚才那个图所示： faher1:=1；faher2:=1；faher3:=1；faher4:=5；faher5:=3至此，我们用上述的算法已经解决

6、了空间的问题，我们不再需要一个n2的空间来记录整 张图的构造，只需要用一个记录数组记录每个结点属于的集合就可以了。但是仔细思考不难发现，每次询问两个元素是否属于同一个集合我们最多还是需要O(n) 的判断！3. 算法3，并查集的路径压缩。 算法2的做法是指就是将元素的父亲结点指来指去的在指，当这课树是链的时候，可见 判断两个元素是否属于同一集合需要O(n)的时间，于是路径压缩产生了作用。路径压缩实际上是在找完根结点之后，在递归回来的时候顺便把路径上元素的父亲指针 都指向根结点。这就是说，我们在“合并5和3”的时候，不是简单地将5的父亲指向3，而是直接指向由此我们得到了一个复杂度只是O(l)的算法

7、。程序清单(1)初始化： for i:=1 to n do fatheri:=i;因为每个元素属于单独的一个集合，所以每个元素以自己作为根结点 (2)寻找根结点编号并压缩路径：function getfather(v : integer) : integer;beginif fatherv=v then exit(v); fatherv:=getfather(fatherv);getfather:=fatherv;end;(3) 合并两个集合：proceudre merge(x, y : integer);beginx:=getfather(x);y:=getfather(y);fatherx

8、:=y;end;(4) 判断元素是否属于同一结合：function judge(x, y : integer) : boolean;beginx:=getfaher(x);y:=gefather(y);if x=y then exit(true)else exit(false);end;这个的引题已经完全阐述了并查集的基本操作和作用。三、并查算法通过对上面引题的分析，我们已经十分清楚所谓并查集算法就是对不相交集合 (disjoint set)进行如下两种操作：(1)检索某元素属于哪个集合； (2)合并两个集合。我们最常用的数据结构是并查集的森林实现。也就是说，在森林中，每棵树代表一个集 合，用

9、树根来标识一个集合。有关树的形态在并查集中并不重要，重要的是每棵树里有那些*元素。1. 合并操作为了把两个集合S和S并起来，只需要把S的根的父亲设置为S的根(或把S的根的父1 2 1 2 2亲设置为S的根)就可以了。1 这里有一个优化：让深度较小的树成为深度较大的树的子树，这样查找的次数就会少些。这个优化称为启发式合并。可以证明：这样做以后树的深度为O(logn)。即：在一个有n个 元素的集合，我们将保证移动不超过logn次就可以找到目标。【证明】我们合并一个有i个结点的集合和一个有j个结点的集合，我们设iWj,我们 在一个小的集合中增加一个被跟随的指针，但是他们现在在一个数量为i + j的集

10、合中。由于:1 + logi = log(i + i) = log(i + j) 所以我们可以保证性质。由于使用启发式合并算法以后树的深度为O(logn)，因此我们可以得出如下性质：启发 式合并最多移动2logn次指针就可以决定两个事物是否想联系。同时我们还可以得出另一个性质：启发式快速合并所得到的集合树，其深度不超过 Llog2n+1，其中n是集合S中的所有子集所含的成员数的总和。【证明】我们可以用归纳法证明：当i=1时，树中只有一个根节点，即深度为1又Llog2l+1二1，所以正确。假设iWn1时成立，尝试证明i=n时成立。不失一般性，可以假设此树是由含有m (1WmWn/2)个元素，根为

11、j的树S ,和含有njm个元素、根为k的树S合并而得到，并且，树j合并到树k,根是k。k(1) 若合并前：子树S的深度V子树S的深度jk则合并后的树深度和Sk相同，深度不超过：bog2(n - m)+ 1显然不超过bog2n+1 ；(2) 若合并前：子树S的深度三子树S的深度jk则合并后的树的深度为Sj的深度+1，即：(Llog2m+1) +1 二 Llog2(2m)+1 = Llog2n+1小结：实践告诉我们，上面所陈述的性质对于一个m条边n个事物的联系问题，最多执 行mlogn次指令。我们只是增加了一点点额外的代码，我们就把程序的效率很大地提升了。 大量的实验可以告诉我们，启发式合并可以在

12、线形时间内解答问题。更确切地说，这个算法 运行时间的花费，很难再有更加明显的优秀、高效的算法了。2. 查找操作查找一个元素u也很简单，只需要顺着叶子到根结点的路径找到u所在的根结点，也就 是确定了 u所在的集合。这里又有一个优化：找到u所在树的根v以后，把从u到v的路径上所有点的父亲都设 置为v，这样也会减少查找次数。这个优化称作路径压缩(compresses paths)。压缩路径可以有很多种方法，这里介绍两种最常用的方法：(1) 满路径压缩(full compresses pa ths)：这是一种极其简单但又很常用的方法。就 是在添加另一个集合的时候，把所有遇到的结点都指向根节点。(2)

13、二分压缩路径(compresses pa ths by halving)：具体思想就是把当前的结点，跳 过一个指向父亲的父亲，从而使整个路径减半深度减半。这种办法比满路径压缩要快那么一 点点。数据越大，当然区别就会越明显。压缩路径的本质使路径深度更加地减小，从而使访问的时候速度增快，是一种很不错的 优化。在使用路径压缩以后，由于深度经常性发生变化，因此我们不再使用深度作为合并操 作的启发式函数值，而是使用一个新的rank数。刚建立的新集合的rank为0，以后当两个 rank相同的树合并时，随便选一棵树作为新根，并把它的rank加1；否则rank大的树作为 新根，两棵树的rank均不变。3. 时

14、间复杂度并查集进行n次查找的时间复杂度是O(na(m,n)(执行n-1次合并和m三n次查找)。其 中a(m,n)是一个增长极其缓慢的函数，它是阿克曼函数(Ackermann Function)的某个反函 数。它可以看作是小于5的。所以可以认为并查集的时间复杂度几乎是线性的。通过上面的分析，我们可以得出：并查集适用于所有集合的合并与查找的操作，进一步 还可以延伸到一些图论中判断两个元素是否属于同一个连通块时的操作。由于使用启发式合 并和路径压缩技术，可以讲并查集的时间复杂度近似的看作0(1)，空间复杂度是O(N)，这样 就将一个大规模的问题转变成空间极小、速度极快的简单操作。(原载九江教育2006年第 1 期)