〖程序清单〗

初始化：

for i:=1 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;

这里有一个优化：让深度较小的树成为深度较大的树的子树，这样查找的次数就会少些。这个优化称为启发式合并。可以证明：这样做以后树的深度为O(logn)。即：在一个有n个元素的集合，我们将保证移动不超过logn次就可以找到目标。 

function judge(x,y:integer):boolean; 

 var fx,fy : integer; 

  begin 

     fx := getfaher(x); 

     fy := gefather(y); 

     If fx=fy then  

       exit(true) else  

       judge := false; 

     if rank[fx]>rank[fy] then 

       father[fy] := fx else begin 

       father[fx] := fy; 

       if rank[fx]=rank[fy] then  

         inc(rank[fy]); 

     end; 

  end; 

初始化：

fillchar(rank,sizeof(rank),0);

并查集的时间复杂度

并查集进行n次查找的时间复杂度是O(n)

它是阿克曼函数（Ackermann Function）的某个反函数。

它可以看作是小于5的。所以可以认为并查集的时间复杂度几乎是线性的。