#创作计划# 并查集基础知识

THUNDER

2025-08-05 21:22:07

发布于：广东

7阅读

0回复

0点赞

声明：本文是把本人在CSDN写的博客搬运过来的

并查集的意义

什么是并查集？要了解并查集的含义，我们首先需要知道它所处理的题目类型，例如家族关系。例：A与B是一家人，B与C是一家人，那A与C就也是一家人。这是直接通过人脑判断的结果，但是如何用代码实现？

此话即出，有的同学就想到了BFS、DFS。额……行是行，但是有点慢。毕竟我们要处理的并不是具体的路径之类的问题。这时候我们其实可以仔细地想一想，建图中所用到的这一些边，它真的全都对的我们查询有用处吗？

这里举一个例子：

我们可以在这个恶心的图里面发现许多冗余的边。假设我们要求3和1是否在一个集合里。用搜索的话可能会去到4；去到5；和去到2。但是我们会发现去到这一些点并不一定对我们求答案有用。比如去到4，会发现过不去，还得回来。而去到5和去到2很明显也已经重复了。由于边多且乱，就会导致点之间的关系也十分混乱，是很浪费时间的。诶！可不可以省去一些边，让这个图更加简单呢？当然可以，这就是最小生成树的内容了。最小生成树的底层逻辑，就是并查集！

你不是点之间关系混乱吗？我就选举出一个祖先节点来做这个家族的代表。且每个节点都有明确的父亲，共同指向一个祖先。这样我们只需要判断两个点是否祖先相同就可以了。至于边，这个更不用说。一个有秩序的家庭不可能出现乱伦（bushi

具体实现：

这里没有看懂的可以去看后面的样例配图解释。

首先我们需要一个father数组来存父亲。

在一开始没有任何关系的时候，等于说是每个点自成一个团体，因此每一个节点的父亲指向自己。这就是初始化。

void init(){
    for(int i = 1;i <= n;i ++){
        fa[i] = i;//所有节点的父亲指向自己
    }
}

嗯？每一个团体的代表不是祖宗吗？怎么这里只有父亲？别急，父亲的父亲一直递归（或while）往上找到自父的节点就是祖宗。这就是求祖宗函数。

int get(int x){
    if(fa[x] == x) return x;//父亲就是自己，证明找到祖先了
    else return get(fa[x]);//往上递归
}

最后，处理合并。如果两个团体要合并了，我们该怎么处理？直接接到尾巴上吗？很明显，这样会使辈分排得很长，查询时浪费时间，因此直接把其中一个（两个都行）的祖先的父亲设为另一个的祖先（即把头连在一起，并合并为一个祖先）。这里不太好理解，我配上一幅图：

合并的代码：

void merge(int x,int y){
    int tmpx = get(x),tmpy = get(y);
    fa[tmpx] = tmpy;//把‘头’连起来
}

模板题：

亲戚

代码：

#include<bits/stdc++.h>
using namespace std;
 
const int N = 5e3 + 5;
int fa[N];
int n,m,p;
 
void init(){
    for(int i = 1;i <= n;i ++){
        fa[i] = i;
    }
}
 
int get(int x){
    if(fa[x] == x) return x;
    else return fa[x] = get(fa[x]);
}
 
void merge(int x,int y){
    int tmpx = get(x),tmpy = get(y);
    if(tmpx != tmpy){
        fa[tmpx] = tmpy;
    }
}
 
int main(){
    cin >> n >> m >> p;
    init();//记得先输入n
    for(int i = 1;i <= m;i ++){
        int u,v;
        cin >> u >> v;
        merge(u,v);//将两点所在集合合并
    }
    while(p --){
        int x,y;
        cin >> x >> y;
        if(get(x) == get(y)) cout << "Yes\n";//祖先相同输出Yes
        else cout << "No\n";
    }
    return 0;
}

路径压缩：

细心的同学会发现我上面求祖宗（get）函数跟前面写得不一样。那是因为我用了一种优化，叫路径压缩。其实并查集在不进行优化时有一个问题。如果这棵树的深度太大，那么查询时就会浪费时间向上寻找祖宗。如果我们把一个根节点的子孙直接指向它，岂不能省很多时间（当然有时不能完全压到深度为2，要看数据）。具体操作只需要在查询时把父节点设为祖宗（具体看上图代码）。