● 并查集 --nju huh - 荔园在线 | 深圳大学学生论坛,荔园晨风BBS,深大在线网站

荔园之美，在春之萌芽，在夏之绽放，在秋之收获，在冬之沉淀

发信人: OneSecond (别问我是谁), 信区: ACMICPC
标  题: 并查集  --nju                          huhaiming
发信站: 荔园晨风BBS站 (Fri Jul 30 20:36:32 2004), 站内信件

发信人: huhaiming (一生只爱她), 信区: Program
标  题: 并查集  --nju
发信站: 荔园晨风BBS站 (Sun May 11 11:30:53 2003), 转信

所谓并查集，它是一个集合，这个集合的元素也是集合，他支持三种操作： MakeSet(x
)，浇立一个只有一个元素x的集合X0，将这个集合放入并查集中； FindSet(x)，在并
查集中寻找一个元素S（注意并查集的元素S也是集合），满足x属于S； Union(x,y)，

将并查集中的元素S1,S2合并，其中x属于S1，y属于S2。
下面说说并查集的实现，其实很简单，用树来实现。所有属于同一集合的元素属于同一
棵树树，这样我们就可以用数根来表示一个集合，要找到某个元素属于哪个集合，只要
找到这个元素所在的树的树根；要合并两个集合，只要合并两棵树。一般比较方便的方
法是用父亲数组Parent[]来表?
树，Parent[i]就是节点i的父结点，树根的父结点就是它本身。这样很容易根据某个节
点找找到他的根，也很容易合并两棵树。但是我们要考虑效率问题。在最坏的情况下，
一棵树退化成一个单链表（想象一下所有的结点只有唯一的儿子节点），这样如果链表
长度为L，从一个节点找到他的
也需要L次运算，对于一共有n个节点元素的并查集，FindSet平均情况和最坏情况下的
复杂杂度都是O(n)，效率并不高。对于一棵树而言，如果树的高度为H，那麽从叶节点只
要经过H次运算就可以找到树根，所以我们应该尽量减少树的高度，最好的情况是树的高
度只有1层，这样就是一个树
下面有很多儿子，这些儿子都是树叶。但是如果两棵这样的树合并，数的高度就会增加
，北热高度为H1的树T1和高度为H2的树T2合并，得到的树的高度有两种情况： max {
H1, H2+1}或者max{H1+1,
H2}，前一种情况是T2的根作为T1的根的儿子，后一种情况则是T1的根作为T2的根的儿子
。照饩退得经过多次Union操作以后，树的高度会增加。为了使得树的高度尽量地小，
我们应该将较矮的树合并到较高的树上，因此我们用一个数rank记录每棵树的高度，ra
nk[i]就是以i为根的子树的高
度，在合并的时候就可以根据rank的值进行合并，Union的代码如下：
     // 合并x,y所在的集合，并返回交集
    int Union(int x, int y)
    {
        x = FindSet( x );          // 找到x所在的树的根
        y = FindSet( y );          // 找到y所在的树的根
        if( x == y ) return x;  // -1表示空集
        if( x == -1 ) return y;
        if( y == -1 ) return x;
        if( Rank[x] > Rank[y] ) {        // 将较低的树合并到较高的树上
            Parent[y] = x;
            return x;
        } else {
            Parent[x] = y;
            if( Rank[x] == Rank[y] ) Rank[y]++;  // 改变树的高度
            return y;
        }
    }
Union其实是一种启发式算法，rank[i]就是启发函数值。
另外，为了降低树的高度，我们在FindSet的时候也会压缩路径，比如原来a是树根，b是
a的
子，c是b的儿子，d是c的儿子，我们调用FindSet(d)找d所在的树的树根，在找的同时
，我
改变该树的结构，使得调用FindSet(d)结束以后树的结构变为a是树根，b是a的儿子，
c也?
a的儿子，d?
彩莂的儿子。这就叫做路经压缩。因此FindSet代码如下：
     // 返回到元素i所属的集合的代表元素, 同时进行路径压缩
    int FindSet(int i)
    {
        if( ( i == -1 ) || ( i >= CAPACITY ) ) {  // -1表示空集
            return -1;
        } else {
            if( ( Parent[i] != -1 ) && (    Parent[i] != i ) )
                Parent[i] = FindSet( Parent[i] ); // 这句话进行路径压缩
            return Parent[i];
        }
    }
并查集的效率很高，可以证明，通过这种树形结构实现的带启发式路径压缩的并查集，
Find
et和Union操作的平均代价是O(lgn)，这和二分查找的复杂度一致，可以证明这已经是理
论?
最好的算法了，不可能有更好的算法了。如果不进行这种路经压缩的话，并查集就退化
成了
表，在同一
链表中的元素属于同一集合，这样的话FindSet的复杂度是O(n)。
并查集也是很常用的数据结构，有一道题目“亲戚”，也要用并查集：
题目：亲戚(Relations)
　　或许你并不知道，你的某个朋友是你的亲戚。他可能是你的曾祖父的外公的女婿的
外甥
的表姐的孙子。如果能得到完整的家谱，判断两个人是否亲戚应该是可行?，但如果两
个?
的最近公共祖先与他们相隔好几代，使得家谱十分庞大，那么检验亲戚关系实非人力所
能及
在这种情况
下，最好的帮手就是计算机。
　　为了将问题简化，你将得到一些亲戚关系的信息，如同Marry和Tom是亲戚，Tom和B
en是
戚，等等。从这些信息中，你可以推出Marry和Ben是亲戚。请写一个程序，对于我们的
关?
亲戚关系的提问，以最快的速度给出答案。
　　参考输入输出格式输入由两部分组成。
　　第一部分以N，M开始。N为问题涉及的人的个数(1 ≤ N ≤ 20000)。这些人的编号
为1,
,3,…,N。下面有M行(1 ≤ M ≤ 1000000)，每行有两个数ai, bi，表示已知ai和bi是亲
戚?
　　第二部分以Q开始。以下Q行有Q个询问(1 ≤ Q ≤ 1 000 000)，每行为ci, di，表
示询
蔯i和di是否为亲戚。
　　对于每个询问ci, di，若ci和di为亲戚，则输出Yes，否则输出No。
　　样例输入与输出
输入relation.in
10 7
2 4
5 7
1 3
8 9
1 2
5 6
2 3
3
3 4
7 10
8 9
输出relation.out
Yes
No
Yes
如果这道题目不用并查集，而只用链表或数组来存储集合，那么效率很低，肯定超时。

--
※ 修改:·huhaiming 於 May 11 11:34:52 修改本文·[FROM: 192.168.0.200]
※ 转载:·荔园晨风BBS站 bbs.szu.edu.cn·[FROM: 192.168.0.200]

荔园在线首页友情链接：深圳大学深大招生荔园晨风BBS S-Term软件网络书店