ACM

简单并查集入门

并查集是一种树型的数据结构,用于处理一些不相交集合(Disjoint Sets)的合并及查询问题。

百度百科

在算法的学习中我们常常遇到这样的一类问题:我们希望能快速查询两个元素是否在一个集合,以及能够快速实现两集合的合并。这种时候我们需要用到并查集这种数据结构。

首先介绍一下并查集的定义:定义f数组,大小为元素个数。f[i]代表与第i号元素处在同一集合的某一个元素的序号,这里我们不妨称f[i]为i的父亲。

初始状态下各个元素之间互不处于一个元素,因此定义结束以后,我们需要初始化f[i]的值为i。 表示i的父亲就是他自己,而不与其他元素有关系。

一个标准的并查集支持两种操作:查询(两个元素是否在同一集合)与合并(将两个集合合并为一个集合)。而实现这两种操作,我们只需要一个函数:find 如下:

int find(int x){
	if (f[x]==x) return x;
	return find(f[x]);
}

对于一个元素x,find函数会不断询问他的父亲,他的父亲的父亲……直到他的某一个祖先的父亲就是他自己为止,然后返回这个祖先的编号。

我们思考这样一个问题,:在这样一个呈现树形的关系图里,如果两个元素的find值相同,是不是意味着这两个元素在同一个集合呢?

答案是肯定的。证明很简单:已知find(x)==z&&find(y)==z,那么有(x和z处于同一个集合)&&(y与z处于同一个集合),即:( x与y处于同一个集合 )。

那么并查集的第一个功能:查询,可以这样写:

bool Query(int x,int y){
	return find(x)==find(y);
}

非常简短,只有一行。那么我们很多时候可以不必要将这个功能写成一个函数,而只需要自己写一个判断就行。ACM比赛中时间紧迫,不必要的代码完全可以不写。

那么如何将两个集合合并为一个集合呢?参考前面的查询函数我们可以发现,只要两个集合里所有的元素的find值都一样就可以了。那么我们只需要让其中一个集合的最终祖先的f值变为另一个集合的最终祖先的序号即可。代码如下

void Union(int x,int y){
	f[find(x)]=find(y);
}

同样也是一行代码。为什么令 f[find(x)]=find(y)就可以让两个集合合并呢?首先y所在集合的元素的find值不会变化,仍然是find(y)。而x所在集合元素的find,会在查询到x之后继续查询到find(y)。那么这样一来就实现了两集合的所有元素的find值都相同了。

并查集的实现到这里就结束了,接下来我们讲并查集的优化。

在数据范围较大的并查集中,find函数往往需要迭代多次,树型结构最坏情况下会退化成链状,时间复杂度会退化为O(n),这是违背我们使用并查集的初衷的。那么我们需要对find函数稍作修改,来优化它的时间复杂度,这里我们直接讲最有效的一种:路径压缩

int find(int x){
	if (f[x]==x) return x;
	f[x]=find(f[x]);
	return f[x];
}

我们增加了一句f[x]=find(f[x]),这样一来find函数在返回结果时,会将find(x)的值赋给我们迭代过程中查询过的每一个点,将这条链优化为一个菊花图。那么接下来我们再次查询这些点的时候可以直接跳转到最终祖先。最后均摊后地时间复杂度是O(logn)。

并查集的代码非常简短,但是背后却蕴含了极为巧妙的思想。下面给出一道例题:HDU1232

我的代码如下(两个版本):

#include<bits/stdc++.h>
using namespace std;
int f[1001],n,m;
int find(int x){
	if (f[x]==x) return x;
	f[x]=find(f[x]);
	return f[x];
}
bool Query(int x,int y){
	return find(x)==find(y);
}
void Union(int x,int y){
	f[find(x)]=find(y);
}
int main(){
    while (scanf("%d%d",&n,&m)&&n){
        for (int i=1;i<=n;i++) f[i]=i;
        int a,b;
        for (int i=1;i<=m;i++){
        	scanf("%d%d",&a,&b);
            if (!Query(a,b)) Union(a,b);
        }
        int ans=0;
        for (int i=1;i<=n;i++)
            if (f[i]==i) ans++;
        printf("%d\n",ans-1);
    }
    return 0;
}
#include<bits/stdc++.h>
using namespace std;
int f[1001],n,m;
int find(int x){
	return f[x]==x?x:f[x]=find(f[x]);
}
int main(){
    while (scanf("%d%d",&n,&m)&&n){
        for (int i=1;i<=n;i++) f[i]=i;
        int a,b;
        for (int i=1;i<=m;i++){
        	scanf("%d%d",&a,&b);
        	f[find(a)]=find(b);
        }
        int ans=0;
        for (int i=1;i<=n;i++)
            if (f[i]==i) ans++;
        printf("%d\n",ans-1);
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注