并查集总结

· · 算法·理论

part 1 什么是并查集

一、集

这里的集是集合的意思,也可以看做是树或是联通块,所以并查集这个算法主要是对集合进行的操作。那怎么存储集合呢？此时我们可以把集合看成树，存储时取任意一个结点作为根结点，通过一个fa[]数组来存储每个节点的祖先就可以了。

二、并

并指的其实就是合并这个操作,主要是把两个不同的集合合并,这里把集合看成树更好理解,合并的大概过程如下图所示：

这里提到了一个并查集中非常重要的一个函数：find(x)

这个函数主要是通过树状的结点连接关系递归来查询根结点的。它的核心代码如下：

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

这里还有一个初始化的问题，在查询的过程中如何判断这个节点是否就是根节点呢？我们可以一开始的时候就把每个结点的祖先初始化为它本身，只要查询到祖先为自己本身的结点就说明它是根结点了。大概过程如下图：

有些题目这样写还是会超时，此时我们就要优化这个递归。我们此时就可以使用路径压缩,它的原理如下图所示：

核心代码如下：

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

三、查

查指的是查询操作，它主要是查询两个不同的结点在不在同一个集合里,核心代码如下：

int t1 = find(x),t2 = find(y);
if(t1 != t2)fa[t1] = t2;

part 2 复杂度

时间复杂度

使用路径压缩之后，并查集的每个操作平均时间几乎为 O(n)

空间复杂度

显然为 O(n) 。

part 3 并查集的应用

例题一：P3367 【模板】并查集

这是一道纯并查集模板题，主要考察并查集的基本操作。

#include <bits/stdc++.h>
using namespace std;
int n,m;
int p[200010];
int find(int x){
    if(x == p[x]){
        return x;
    }
    return p[x] = find(p[x]);
}
int main(){
    cin>>n>>m;
    for(int i = 1;i<=n;i++){
        p[i] = i;
    }
    int x,y,z;
    while(m--){
        cin>>z>>x>>y;
        x = find(x);
        y = find(y);
        if(z == 1){
            p[x] = y;
        }else{
            if(x == y)cout<<"Y"<<'\n';
            else cout<<"N"<<'\n';
        }
    }
    return 0;
}

例题二：P1955 [NOI2015] 程序自动分析

这道题我们可以先把相等的变量放在同一个集合里，输入完后再扫描一遍不相等的关系，再判断有没有冲突。

#include <bits/stdc++.h>
using namespace std;
int t;
map<int,int>p;
int find(int x){
    if(p[x] == x)return x;
    return p[x] = find(p[x]);
}
int x[110000],y[110000],e[110000];
int main(){
    cin>>t;
    while(t--){
        p.clear();
        int n;
        cin>>n;     
        for(int i = 1;i<=n;i++){
            cin>>x[i]>>y[i]>>e[i];
            if(!p[x[i]])p[x[i]] = x[i];
            if(!p[y[i]])p[y[i]] = y[i];         
            if(e[i]){           
                p[find(x[i])] = find(y[i]);
            }       
        }
        bool flag = 0;
        for(int i = 1;i<=n;i++){
            if(!e[i]){
                if(find(x[i]) == find(y[i])){
                    flag = 1;
                    break;
                }
            }
        }
        if(flag)cout<<"NO\n";
        else cout<<"YES\n";
    }
    return 0;
}

其他应用

最小生成树算法 中的 Kruskal 和 最近公共祖先 中的 Tarjan 算法是基于并查集的算法。

例题

习题