【狂热算法篇】并查集：探秘图论中的 “连通神器”，解锁动态连通性的神秘力量

用户11458826

发布于 2025-01-23 19:00:58

10200

代码可运行

文章被收录于专栏：杀马特杀马特

运行总次数：0

代码可运行

一·概念：

并查集是一种树型的数据结构，用于处理不相交集合的合并及查询问题。它主要支持两种操作：“并”（Union）操作，即将两个不相交的集合合并为一个集合；“查”（Find）操作，即查找元素所在的集合（大概它的外形也可以理解为多插树的形式）。
并查集在解决元素分组和动态连通性问题上展现出强大的能力，能够高效地处理元素之间的关系，判断元素是否属于同一集合，以及将不同集合进行合并操作。

这里我们就记住：同根就连通，合并总发生在根上。

二·数据结构表示：

数组存储：

最常见的实现方式是使用一个数组 pre[] 来存储每个元素的父节点信息。初始时，每个元素自成一个集合，所以 pre[i] = i，表示元素 i 是它自己集合的代表元素即根节点.

当然了，还会有其他表示方法：

也可以使用链表、树等数据结构表示并查集，但数组是最常用的，因为其实现简单，操作相对便捷，并且在经过优化后可以达到理想的性能。

三·基本操作及实现：

3.1初始化：

void init() {
    for (int i = 1; i <= n; i++) {
        pre[i] = i;//无连接把自身初始化成前驱节点
    }
    return;
}

这里就不用多解释了把，一开始还没给关系，它们每个节点自己就是一个集合，自己是自己的根节点。

3.2查找操作（root）：

功能：查找元素所在集合的代表元素（根节点）。

通过不断查找元素的父节点，直到找到父节点为自身的元素，该元素即为集合的代表元素。

这里我们可以用循环来实现也可以用递归；但是如果它深度太高还是循环比较友好，但是一般数据又不会太大。

比如我们举个例子：

例如，对于集合 {0, 1, 2}，其中 pre[0] = 0, pre[1] = 0, pre[2] = 1，查找元素 2 的根节点时，先找到 pre[2] = 1，继续查找 pre[1] = 0，最终找到根节点为 0。

下面就用普通的递归实现我们的查找操作：

int root(int x) {
     return pre[x]==x?x:root(pre[x]);//递归找到根节点
}

3.3 合并操作（merge）：

功能：将两个元素所在的集合合并为一个集合。

首先找到两个元素的根节点，如果根节点不同，则将其中一个根节点作为另一个根节点的子节点，完成集合的合并。

注意：合并操作不是就是找根节点嘛，这里我们可以规定方向但是也可以不规定：前提是，我们保证所合并的集合的每个节点的通过父亲节点找到的根节点一定是同一个即可。（但是对于朴素法，也就是我们上面所写的，还没有做优化，可以认为后者的根节点点是前者的根节点的根节点）

下面就是简单版本的合并：

void merge(int i, int j) {
    int x = root(i), y = root(j);
    pre[x]=y;
    return;
}

这样就是实现好了。其实上面实现的就是我们的朴素版本。

朴素版：

const int N = 5005;

/// <summary>
/// 多插树
/// </summary>
int pre[N];//类似前驱节点，pre[i]是i指向的前一个节点j：i->j
int rk[N];//每个节点的秩：高度
int sz[N];//以i号节点作为根节点的集合的节点个数
int n, m, p;

void init() {
    for (int i = 1; i <= n; i++) {
        pre[i] = i;//无连接把自身初始化成前驱节点
    }
    return;
}
//找根节点：
int root(int x) {
     return pre[x]==x?x:root(pre[x]);//递归找到根节点
}
//合并总发生在根节点：
void merge(int i, int j) {
    int x = root(i), y = root(j);
    pre[x]=y;
    return;
}

但是这样肯定是时间复杂度肯定比较高的，可以认为为O(N)；那么下面我们来介绍一下它的优化策略。

四.优化策略:

下面我们分三种情况来把朴素版给优化一下：

4.1路径压缩：

介绍：在查找操作时，将查找路径上的元素的父节点都直接指向根节点，以减少后续查找的时间复杂度。

那么我们只需要，在查找元素的根节点时，将路径上的元素的父节点直接更新为根节点。

也就是我们最后的目的就是让每个点的父亲节点都是他们的根节点即可。

当然了它的实现可以是循环解决也可以是递归，但是对于数据不是特别大，我们就选递归，因为它比较好写：

//找根节点：
int root(int x) {
   return pre[x]=pre[x] == x ? x : root(pre[x]);//递归找到根节点,归的时候完成对当前节点的最终指向（根节点）
   
}

这个优化只需要我们更改找根操作即可，其他和朴素法一样。

但是这样就一定好嘛，我们之前说的是它是一个多插树，这样就破坏了，树的结构，当然也是可以用的（只限于单个数据结构，也就是只有它自己）；但是如果还要和其他数据结构的功能配合使用，那么就麻烦了；因此我们就要建议使用后面的优化方法了。

时间复杂度就降到O(1)了。

总代码：

const int N = 5005;

/// <summary>
/// 多插树
/// </summary>
int pre[N];//类似前驱节点，pre[i]是i指向的前一个节点j：i->j
int rk[N];//每个节点的秩：高度
int sz[N];//以i号节点作为根节点的集合的节点个数
int n, m, p;

路径压缩：破坏树结构

void init() {
    for (int i = 1; i <= n; i++) {
        pre[i] = i;//无连接把自身初始化成前驱节点
    }
    return;
}
//找根节点：
int root(int x) {
   return pre[x]=pre[x] == x ? x : root(pre[x]);//递归找到根节点,归的时候完成对当前节点的最终指向（根节点）
   
}
//合并总发生在根节点：
void merge(int i, int j) {
    int x = root(i), y = root(j);
    pre[x] = y;
    return;
}

4.2按秩合并：

目的：避免合并操作使树变得过于不平衡，影响查找性能。

为每个节点维护一个秩（rank），可以是树的高度或集合的大小，即叶子节点秩为0，合并时将秩小的集合合并到秩大的集合，秩相等时任意合并并更新秩。

说白了也就是让我们的这颗树变的矮一点，胖一点而不是高高瘦瘦的；那这样为什么能起到优化作用呢？

我们的秩就是树高，如果我们让秩小的和并时候指向高的，也就是让高树的根节点成为矮树根节点的父亲节点；这样我们在查询高树的N多个底层节点的时候就可以少走一次了；矮树多走一步，但是它相对走的少啊。

那么这就得出结论了：

让秩小的根节点指向秩大的根节点；如果相同呢？那么随便指向，但是此时我们就要更新最终根节点的秩，也就是加一了（这里其实就不完全考虑我们上面朴素法定义的关系指向了，只需要保证同集合共根即可）。

时间复杂度就近似O(logN)了。

定义rk数组存放每个节点的秩：

void merge(int i, int j) {
    int x = root(i), y = root(j);
       if (rk[x] < rk[y]) swap(x, y);
       //保证x的秩大。秩大的指向秩小的：（根节点）
       pre[y] = x;
       if (rk[x] == rk[y])rk[x]++;//如果相等则根节点可以互相指向，但是被指向的节点秩要更新
    return;
}

然而这里我们只需要更改合并操作；对于查找的操作（我们也可以修改成循环形式）：

总代码：

const int N = 5005;

/// <summary>
/// 多插树
/// </summary>
int pre[N];//类似前驱节点，pre[i]是i指向的前一个节点j：i->j
int rk[N];//每个节点的秩：高度
int sz[N];//以i号节点作为根节点的集合的节点个数
int n, m, p;

/// /按秩合并：根据高度关系让root函数查找的时候找的更快（每个节点都少走一个，提高效率）
void init() {
for (int i = 1; i <= n; i++) {
    pre[i] = i;//无连接把自身初始化成前驱节点
}
return;
}
//找根节点：
int root(int x) {
    //return pre[x] == x ? x : root(pre[x]);//递归找到根节点
    while (pre[x] != x) x = pre[x];
    return x;
}
//合并总发生在根节点：
void merge(int i, int j) {
    int x = root(i), y = root(j);
       if (rk[x] < rk[y]) swap(x, y);
       //保证x的秩大。秩大的指向秩小的：（根节点）
       pre[y] = x;
       if (rk[x] == rk[y])rk[x]++;//如果相等则根节点可以互相指向，但是被指向的节点秩要更新
    return;
}

4.3按大小合并（启发合并）：

这里其实和按秩排序优化效果上一样；只不过不是根据秩划分；而是根据集合的大小来划分罢了。

就是我们合并的时候，肯定会有多个集合；那么我们要想集合里的元素越多，那么它向上找根次数肯定越多，那么如果一个大集合和一个小集合合并是不是让大集合的根指向小集合的根就可以少走很多次了（类似按秩合并思想，只是写法不同罢了）

时间复杂度就近似O(logN)了。

因此得到总结：

小集合根节点指向大集合根节点；如果相同，两个根节点可以随机指向；其次注意合并后要更新集合大小。

因此我们搞一个数组为sz[]记录每个集合大小：

也就是：int sz[N];以i号节点作为根节点的集合的节点个数。

但是这里还有个细节（很容易忽略）:我们这个操作不仅要改变指向，集合大小，还要注意初始化，每个节点一开始的集合大小就是1；不像按秩合并一样（因为叶子节点本身秩就是0）：

void init() {
    for (int i = 1; i <= n; i++) {
        pre[i] = i;//无连接把自身初始化成前驱节点
        sz[i] = 1;//注意数组含义（集合节点数）/细节/
    }
    return;
}

合并：

void merge(int i, int j) {
    int x = root(i), y = root(j);
    if (sz[x] < sz[y]) swap(x, y);
    //保证x是大集合：
    pre[y] = x;
    sz[x] += sz[y];//有y集合的纳入，x变大，的sz也增大
    return;
}

总代码：

const int N = 5005;

/// <summary>
/// 多插树
/// </summary>
int pre[N];//类似前驱节点，pre[i]是i指向的前一个节点j：i->j
int rk[N];//每个节点的秩：高度
int sz[N];//以i号节点作为根节点的集合的节点个数
int n, m, p;

/// /按大小合并（启发合并）：
void init() {
    for (int i = 1; i <= n; i++) {
        pre[i] = i;//无连接把自身初始化成前驱节点
        sz[i] = 1;//注意数组含义（集合节点数）/细节/
    }
    return;
}
//找根节点：
int root(int x) {
   // return pre[x] == x ? x : root(pre[x]);//递归找到根节点
    while (pre[x] != x) x = pre[x];
    return x;
}
//合并总发生在根节点：
void merge(int i, int j) {
    int x = root(i), y = root(j);
    if (sz[x] < sz[y]) swap(x, y);
    //保证x是大集合：
    pre[y] = x;
    sz[x] += sz[y];//有y集合的纳入，x变大，的sz也增大
    return;
}

五·优化前后对比：

5.1 优化前：

单次查找或合并操作的最坏情况时间复杂度为 o(N)，因为树可能退化成链，查找元素时可能需要遍历整个链。

5.2优化后：

经过路径压缩和按秩合并优化，单次查找或合并操作的平均时间复杂度接近o（

（N）），其中

（N）是阿克曼函数的反函数，其增长速度非常慢，在实际应用中可近似认为是常数时间复杂度，因此优化后的并查集在效率上有显著提升。

六·例题测试：

下面我们就以一道洛谷的并查集模版题测试一下吧：

输入：

输出：

Yes
Yes
No

数据范围（还是比较小的）：

链接： 亲戚 - 洛谷

首先我们每个写法无论优化还是不优化都是可以通过的：

这里数据范围比较小，所以优化肯定是成立的但是我们一般看不太出来：

这里按大小合并确实有点离谱了，但是数据还是比较少的；因此理论应该是和按秩合并一样的。

main函数实现:

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);//取消同步
    cin >> n >> m >> p;
    init();//初始化，自己指向自己
    while (m--) {
        int i, j;
        cin >> i >> j;
        merge(i, j);//合并：完成节点的指向i->j。
    }
    while (p--) {
        int a, b;
        cin >> a >> b;
        if (root(a) == root(b)) cout << "Yes" << endl;//根节点相同属于同一个节点
        else cout << "No" << endl;
    }

}