并查集算法

简介&适用场景

如果有m个集合,每个里面有若干个元素,要反复查找一个元素在哪个集合中,或者查询a与b是否属于同一个集合,并查集就是完成这种操作的数据结构。

实现原理

每一个集合都有一个或多个元素,从每个集合中选出一个元素作为它的代表,我们就可以很快地找出元素对应集合(的代表),或者合并两个集合。

这里我们可以用树来表示集合,树的每个节点代表集合中的一个元素,树的根节点就是集合的代表,如图:

union-set-1

//自己画的,不好看别喷,同下

图中有两个集合,一个是{a,b,c,d},代表为a,另一个是{e,f,g},代表为e

节点表示一个元素,每个节点有一个指针来指向父节点,根节点(代表)的指针指向自己。这样,沿着每个节点的父节点不断向上查找,最终一定可以找到根节点,也就是集合的代表。

创建并查集

int uset[MAXN]; // uset[x]表示x的父节点
void buildSet(int size) {
    for(int i = 0; i < size; i++)
        uset[i] = i;
}

buildSet(int)的时间复杂度为O(n),通过执行buildSet(int),我们会得到这样一个并查集森林,每个元素都是一个单元素集合,父节点都是自身:

union-set-2

查找集合的代表

在并查集森林中,每个集合的代表即是集合的根节点。“查找”根据其父节点的指针向上查找直到到底树根。代码实现如下:

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

这样做的时间复杂度是树的高度,频繁查找时显然过于复杂,这里我们只需要应用一种简单而有效的策略——路径压缩。每次查找时,我们都让路径上的每个节点都直接指向根节点,如图:

union-set-3

为了达到这样的效果,find递归地经过树,改变每一个节点的引用到根节点。得到的树将更加扁平,为以后直接或者间接引用节点的操作加速。以下是它的递归实现:

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

每个操作的平均时间仅为O(α(n))α(n)n=f(x)=A(x,x)的反函数,其中A是急速增加的阿克曼函数,因为α(n)是它的反函数,故α(n)在n十分巨大的时候(1e6)十分巨大时还是小于5。因此,平均运行时间是个极小的常数。

合并集合

合并操作很简单,找到两个集合的代表(根节点),再将它们用指针连接起来。代码实现如下:

void unionu(int a,int b) {
    if((a = find(a)) == (b = find(b))) return;
    uset[a] = b;
}

水题

洛谷P1551 亲戚

这道题基本上是并查集的模板题,只需要把刚才的代码复制一遍把并查集实现一下就可以过了。

先创建一个大小为n的并查集,接下来m行根据输入合并集合,最后判断两个人是否在同一个集合中。C++的AC代码如下:

#include <iostream>
#define MAXN 5002
using namespace std;

int uset[MAXN];
int n,m,p,i,j,mi,mj;

void MakeSet(int sz) {
    for(i=0;i<sz;i++) uset[i] = i;
}

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

void unionu(int a,int b) {
    if((a = find(a)) == (b = find(b))) return;
    uset[a] = b;
}

int main()
{
    cin>>n>>m>>p;
    MakeSet(n);
    for(i=0;i<m;i++) {
        cin>>mi>>mj;
        if(find(mi) != find(mj)) unionu(mi,mj);
    }
    for(i=0;i<p;i++) {
        cin>>mi>>mj;
        if(find(mi) == find(mj)) cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    return 0;
}

参考

并查集 Wikipedia - https://zh.wikipedia.org/wiki/%E5%B9%B6%E6%9F%A5%E9%9B%86

洛谷

本页面的全部内容在 CC BY-NC-SA 4.0 协议之条款下提供,附加条款亦可能应用
本文链接:https://www.copperion.com/2017/union-find-data-structure/