并查集

最近在打warfare，顺便学了下并查集以及最大生成树（最小生成树同），AC完就很傲娇地来这里写题解啦~\(≧▽≦)/~啦啦啦

恩...首先先说下并查集的原理：

并查集的实现分为三个基本操作：初始化，合并，查询。

    1.初始化

    初始时，把所有元素各放在一个独立的集合里，每个元素形成一棵独立的树，多个元素形成多棵树，构成森林。用father[i]表示i元素的父亲结点，初始时，每个元素的父亲结点是它本身，定义为father[i]=i。

    Procedure init;

       for i←1 to n do

            father[i]←i;

    2.合并

    当某两个元素u,v不在同一棵树中，需要合并时，方法为分别找到u、v最远的祖先结点编号，即u、v各所在树的树根，在树根之间连一条边，让u的树根指向v的树根，将两棵树合并成一棵树。合并过程如图5-1所示：

    合并过程的算法实现时，用一个递归函数getFather(u)寻找u结点的树根，用一个过程union(u,v)合并u,v所在的树。具体实现如下：

    Function getFather(u:longint):longint;

       //寻找结点所在的树根

       if father[u]=u then

           exit(u)

       else

           getFather←getFather(father[u]);

    Procedure union(u,v:longint);  //合并两棵树

       fu←getFather[u];

       fv←getFather[v];

       if fu<>fv then

          father[fu]←fv;

    3.查询

    要查询两个元素u,v是否在同一集合时，可以查询u,v的父亲的父亲（即最远祖先）的编号是否一样，如一样，u,v在同一集合中，不一样的话，u,v在不同的集合中。用一个函数query(u,v)来实现。

    Function query(u,v:longint):boolean;

       if getfahter[u]=getfather[v] then

          exit(true)

       else

           exit(false);

   由并查集算法的3个过程可知，并查集算法的时间复杂度主要体现在寻找根结点上。在使用递归算法寻找树根时，时间复杂度为树的层次O（logn）；当元素非常多，树易退化成一链时，每次查询都有O（n）的时间复杂度，相当于在一集合中枚举每一个点了，算法的效率有点低下。我们可以对其进行改进。

并查集,布布扣,bubuko.com

并查集

原文：http://www.cnblogs.com/polebug/p/3619660.html