信息学奥赛中的特殊数据结构——并查集
在一些有N个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查一个元素在哪个集合中。这一类问题近几年来反复出现在信息学的国际国内赛题中，其特点是看似并不复杂，但数据量极大，若用正常的数据结构来描述的话，往往在空间上过大，计算机无法承受；即使在空间上勉强通过，运行的时间复杂度也极高，根本就不可能在比赛规定的运行时间（1～3秒）内计算出试题需要的结果，只能采用一种全新的抽象的特殊数据结构——并查集来描述。
一、数学准备
首先，我们从数学的角度给出等价关系和等价类的定义：
定义1：如果集合S中的关系R是自反的，对称的，传递的，则称他为一个等价关系。
——自反：x＝x；
——对称：若x＝y，则y＝x；
—
—传递：若x＝y、y＝z，则x＝z。
要求：x、y、z必须要同一个子集中。
定义2：如果R是集合S的等价关系。对于任何x∈S，由[x]R＝{y|y∈S and xRy}给出的集合[x]R称为由x∈S生成的一个R的等价类。
定义3：若R是集合S上的一个等价关系，则由这个等价关系可产生这个集合的唯一划分。即可以按R将S划分为若干不相交的子集S1，S2，S3，S4，……，他们的并即为S，则这些子集Si变称为S的R等价类。
划分等价类的问题的提法是：要求对S作出符合某些等价性条件的等价类的划分，已知集合S及一系列的形如“x等价于y”的具体条件，要求给出S的等价类的划分，符合所列等价性的条件。（我们上面提到的联系，即可认为是一个等价关系，我们就是要将集合S划分成n个联系的子集，然后再判断x，y是否在一个联系子集中。）
二、引题——亲戚（relation）
【问题描述】若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，现在给出某个亲戚关系图，求任意给出的两个人是否具有亲戚关系。
规定：x和y是亲戚，y和z是亲戚，那么x和z也是亲戚。如果x,y是亲戚，那么x的亲戚都是y的亲戚，y的亲戚也都是x的亲戚。（人数≤5000，亲戚关系≤5000，询问亲戚关系次数≤5000）。
【算法分析】
1. 算法1，构造图论模型。
用一个n*n的二维数组描述上面的图形，记忆各个点之间的关系。然后，只要判断给定的两个点是否连通则可知两个元素是否有“亲戚”关系。
但要实现上述算法，我们遇到两个困难：
（1）空间问题：需要n2的空间，而n高达5000！
（2）时间问题：每次判断连通性需要O(n)的处理。
该算法显然不理想。
并查集多用于图论问题的处理优化，我们看看并查集在这里的表现如何。
2. 算法2，并查集的简单处理。
我们把一个连通块看作一个集合，问题就转化为判断两个元素是否属于同一个集合。
假设一开始每个元素各自属于自己的一个集合，每次往图中加一条边a－b，就相当于合并了两个元素所在集合A和B，因为集合A中的元素用过边a－b可以到达集合B中的任意元素，反之亦然。
当然如果a和b本来就已经属于同一个集合了，那么a-b这条边就可以不用加了。
（1）具体操作：
① 由此用某个元素所在树的根结点表示该元素所在的集合；
② 判断两个元素时候属于同一个集合的时候，只需要判断他们所在树的根结点是否一样即可；
③ 也就是说，当我们合并两个集合的时候，只需要在两个根结点之间连边即可。
（2）元素的合并图示：
① 合并1和2
② 合并1和3
③ 合并5和4
④ 合并5和3
（3）判断元素是否属于同一集合：
用father[i]表示元素i的父亲结点，如刚才那个图所示：
faher[1]:=1；faher[2]:=1；faher[3]:=1；faher[4]:=5；faher[5]:=3
至此，我们用上述的算法已经解决了空间的问题，我们不再需要一个n2的空间来记录整张图的构造，只需要用一个记录数组记录每个结点属于的集合就可以了。
但是仔细思考不难发现，每次询问两个元素是否属于同一个集合我们最多还是需要O(n)的判断！
3. 算法3，并查集的路径压缩。
算法2的做法是指就是将元素的父亲结点指来指去的在指，当这课树是链的时候，可见判断两个元素是否属于同一集合需要O(n)的时间，于是路径压缩产生了作用。
路径压缩实际上是在完根结点之后，在递归回来的时候顺便把路径上元素的父亲指针都指向根结点。
这就是说，我们在“合并5和3”的时候，不是简单地将5的父亲指向3，而是直接指向根节点1，如图：
由此我们得到了一个复杂度只是O(1)的算法。
〖程序清单〗
（1）初始化：
for i:=1 to n do father[i]:=i;
因为每个元素属于单独的一个集合，所以每个元素以自己作为根结点。
（2）寻根结点编号并压缩路径：
function getfather(v : integer) : integer;
begin
if father[v]=v then exit(v);
father[v]:=getfather(father[v]);
getfather:=father[v];
end;
（3）合并两个集合：
proceudre merge(x, y : integer);
begin
x:=getfather(x);
y:=getfather(y);
father[x]:=y;
end;
（4）判断元素是否属于同一结合：
function judge(x, y : integer) : boolean;
begin
x:=getfaher(x);
y:=gefather(y);
if x=y then exit(true)
else exit(false);
end;
这个的引题已经完全阐述了并查集的基本操作和作用。
三、并查算法
通过对上面引题的分析，我们已经十分清楚——所谓并查集算法就是对不相交集合（disjoint set）进行如下两种操作：
（1）检索某元素属于哪个集合；
（2）合并两个集合。
我们最常用的数据结构是并查集的森林实现。也就是说，在森林中，每棵树代表一个集合，用树根来标识一个集合。有关树的形态在并查集中并不重要，重要的是每棵树里有那些元素。
1. 合并操作
为了把两个集合S1和S2并起来，只需要把S1的根的父亲设置为S2的根（或把S2的根的父亲设置为S1的根）就可以了。
这里有一个优化：让深度较小的树成为深度较大的树的子树，这样查的次数就会少些。这个优化称为启发式合并。可以证明：这样做以后树的深度为O(logn)。即：在一个有n个元素的集合，我们将保证移动不超过logn次就可以到目标。
【证明】我们合并一个有i个结点的集合和一个有j个结点的集合，我们设i≤j，我们在一个小的集合中增加一个被跟随的指针，但是他们现在在一个数量为i＋j的集合中。由于：
所以我们可以保证性质。
由于使用启发式合并算法以后树的深度为O(logn)，因此我们可以得出如下性质：启发式合并最多移动2logn次指针就可以决定两个事物是否想联系。
同时我们还可以得出另一个性质：启发式快速合并所得到的集合树，其深度不超过，其中n是集合S中的所有子集所含的成员数的总和。
【证明】我们可以用归纳法证明：
当i=1时，树中只有一个根节点，即深度为1
又，所以正确。
假设i≤n－1时成立，尝试证明i＝n时成立。
不失一般性，可以假设此树是由含有m（口袋的天空1≤m≤n/2）个元素，根为j的树Sj，和含有n－m个元素、根为k的树Sk合并而得到，并且，树j合并到树k，根是k。
（1）若合并前：子树Sj的深度＜子树Sk的深度
则合并后的树深度和Sk相同，深度不超过：
显然不超过；
（2）若合并前：子树Sj的深度≥子树Sk的深度
则合并后的树的深度为Sj的深度+1，即：
小结：实践告诉我们，上面所陈述的性质对于一个m条边n个事物的联系问题，最多执行mlogn次指令。我们只是增加了一点点额外的代码，我们就把程序的效率很大地提升了。大量的实验可以告诉我们，启发式合并可以在线形时间内解答问题。更确切地说，这个算法运行时间的花费，很难再有更加明显的优秀、高效的算法了。
2. 查操作
查一个元素u也很简单，只需要顺着叶子到根结点的路径到u所在的根结点，也就是确定了u所在的集合。
发布评论