文档介绍：特殊数据结构一一并查集
在一些有N个元素的集合应用问题中，我们通常是在开始时让每个元素构成 一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间 要反复查找一个元素在哪个集合中。这一类问题近几年来反复出现在信息学的国 际to n do father[i]:=i;
因为每个元素属于单独的一个集合，所以每个元素以自己作为根结点。
寻找根结点编号并压缩路径：
function getfather(v : integer) : integer;
begin
if father[v]=v then exit(v);
father[v]:=getfather(father[v]);
getfather:二father[v];
end;
合并两个集合：
proceudre merge(x, y : integer);
begin
x:=getfather(x);
y:=getfather(y);
father[x]:=y;
end;
判断元素是否属于同一结合：
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)进行如下两种操作:
检索某元素属于哪个集合；
合并两个集合。
我们最常用的数据结构是并查集的森林实现。也就是说，在森林中，每棵树 代表一个集合，用树根来标识一个集合。有关树的形态在并查集中并不重要，重 要的是每棵树里有那些元素。
合并操作
为了把两个集合S和S并起来，只需要把S的根的父亲设置为S的根(或把
1 2 1 2
S2的根的父亲设置为S1的根)就可以了。
2这里有一个优化：让深度较小的树成为深度较大的树的子树，这样查找的次 数就会少些。这个优化称为启发式合并。可以证明：这样做以后树的深度为 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的树 j和含有n — m个元素、根为k的树Sk合并而得到，并且，树j合并到树k， 根是ko
若合并前：
则