ZZ并查集

原文出处：http://blog.sina.com.cn/s/blog_5ec05ef30100cp7f.html

作者：angela

 

所谓并查集，它是一个集合，这个集合的元素也是集合，他支持三种操作
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记录每棵树的高度，rank[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也是a的儿子。这就叫做路经压缩。因
此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];
}
}

并查集的效率很高，可以证明，通过这种树形结构实现的带启发式路径压缩的并查
集，FindSet和Union操作的平均代价是O(lgn)，这和二分查找的复杂度一致，可以
证明这已经是理论上最好的算法了，不可能有更好的算法了。如果不进行这种路经
压缩的话，并查集就退化成了链表，在同一链表中的元素属于同一集合，这样的话
FindSet的复杂度是O(n)。

并查集也是很常用的数据结构，有一道题目“亲戚”，也要用并查集：

题目： 亲戚(Relations)

　　或许你并不知道，你的某个朋友是你的亲戚。他可能是你的曾祖父的外公的女
婿的外甥女的表姐的孙子。如果能得到完整的家谱，判断两个人是否亲戚应该是可
行的，但如果两个人的最近公共祖先与他们相隔好几代，使得家谱十分庞大，那么
检验亲戚关系实非人力所能及。在这种情况下，最好的帮手就是计算机。

　　为了将问题简化，你将得到一些亲戚关系的信息，如同Marry和Tom是亲戚，
Tom和Ben是亲戚，等等。从这些信息中，你可以推出Marry和Ben是亲戚。请写一个
程序，对于我们的关于亲戚关系的提问，以最快的速度给出答案。

　　参考输入输出格式 输入由两部分组成。

　　第一部分以N，M开始。N为问题涉及的人的个数(1 ≤ N ≤ 20000)。这些人的
编号为1,2,3,…,N。下面有M行(1 ≤ M ≤ 1000000)，每行有两个数ai, bi，表示
已知ai和bi是亲戚。

　　第二部分以Q开始。以下Q行有Q个询问(1 ≤ Q ≤ 1 000 000)，每行为ci,
di，表示询问ci和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
如果这道题目不用并查集，而只用链表或数组来存储集合，那么效率很低，肯定超
时。