小指针

V1

2022/10/16阅读:14主题:凝夜紫

【数据结构】看完必会的并查集入门攻略2.0

本文是前文的升级版本,在前文的基础上,增加了更详细的讲解,将实现过程分步描述,并且将前文的python实现改成了cpp的实现。

并查集是一种思路巧妙,代码很短的数据结构,也因此常常在算法题或者面试中出现。下面我们以一个模板题目作为示例,详细描述并查集的基本原理及使用。

AcWing 836. 合并集合

一共有 n 个数,编号是 1∼n,最开始每个数各自在一个集合中。

现在要进行 m 个操作,操作共有两种:

M a b,将编号为 a 和 b 的两个数所在的集合合并,如果两个数已经在同一个集合中,则忽略这个操作; Q a b,询问编号为 a 和 b 的两个数是否在同一个集合中;

输入格式
第一行输入整数 n 和 m。

接下来 m 行,每行包含一个操作指令,指令为 M a b 或 Q a b 中的一种。

输出格式
对于每个询问指令 Q a b,都要输出一个结果,如果 a 和 b 在同一集合内,则输出 Yes,否则输出 No。

每个结果占一行。

数据范围

1≤n,m≤105

输入样例

4 5
M 1 2
M 3 4
Q 1 2
Q 1 3
Q 3 4

输出样例

Yes
No
Yes

题目描述

有n个数,编号1~n。现在有两个操作:

  1. M(merge)。合并两个数到一个集合中,如M a b,则表示a和b合并到一个集合。

  2. Q(query)。查询两个数是否在一个集合,如Q a b,查询a和b是否在一个集合当中。

题目分析

分为常规思路并查集两部分,读者可以对比这两种方法的不同,来初步理解并查集的作用。

常规思路

如果对于两个数,每个数初始都自己占用一个集合,那么合并两个数就将其中一个数的所属集合变为另外一个,但是这样做,在查询的时候则必须遍历两个数的所属集合,所以单次查询的时间复杂度是O(n)。

使用并查集

概念

并查集,从名字中也可以看出来,这是一个专门负责 合并与查询 的数据结构

在并查集中,使用多叉树的形式来维护所有的集合。使用根节点的编号来作为整个集合的编号,每个节点存储它的父节点,根节点存储它自己。用p[x]表示x的父节点编号。

  1. 白色数字:父节点编号;

  2. 绿色数字:节点本身的编号;

概念图
概念图

在这里,我们需要明确集合与节点是包含关系

  1. 用集合的根节点编号表示一个集合。比如,也就是初始化之后,1号节点因为它的节点编号和父节点编号相同,因此它就是一个集合的根节点,因为它的节点编号是1,所以该集合的编号也是1。

    所以,后文所说的"集合1",就是代表以1号节点为根节点的整个集合。在上图中,这个集合包含七个元素(未合并前)。

操作:初始化

为了方便后续的并和查的操作,我们在初始化阶段让每个节点都属于一个单独的集合,实现上就是节点编号等于它的父节点编号,如:节点1的父节点也是1。

// 初始化n个集合,每个集合i只有节点i一个元素。
for (int i = 1; i <= n; i ++ ) 
    p[i] = i;

操作:合并

合并两个节点a和b。直接将一个节点的所在集合 指向 另外一个节点的所在集合。

如下图,我们把节点2合并到节点1,既,集合2的父节点编号 变成 集合1的节点编号

// 找到a和b的所属集合
int x = find(a), y = find(b);
// 下面两种方式均是把两个点合并到同一个集合
p[x] = y; // x的父节点是y
p[y] = x; // y的父节点是x

操作:查找

找到元素x属于哪个集合(也就是find函数)。我们沿着x的父节点一直向上搜索,直到找到x的最终根节点

  1. 根据初始化的规则,我们可以直观的知道,判断一个点是不是最终根节点,实际上就是在看一个点的编号 是否等于 它的父节点的编号。用代码表示就是(p[i] == i)

  2. 经过合并之后,节点的所属集合就会改变

    如图中节点2的所属集合本来是它自己,但是我们合并之后,把整个集合2合并到集合1上,所表现出来的现象就是原本节点2的父节点是它自己(2) 表示它是集合2的最终根节点,合并之后节点2的父节点变成了节点1,它的父节点不再是它自己,所以它也再属于集合2

    那么,如何找到节点2合并后属于哪个集合呢?

    我们只要沿着它的父节点向上找,直到找到最终根节点(参考概念图中天蓝色的文字描述部分)。

    // 当循环停止之后,x就是所属的集合。
    while (p[x] != x)  
        x = p[x];

优化:路径压缩

以概念图为例。

我们发现在查找这个操作上,我们要沿着父节点一点点的向上查找,直到找到最终根节点为止。

比如,找到节点7的所属集合,需要查找四次。这个查找次数和树的高度是成正比例的,也就是说所需要的时间复杂度是log(n)级别的。

而有一种优化方式,可以把这个复杂度优化到O(1)级别。在合并的时候,我们直接让所有的节点的父节点都指向所在集合的根节点

这种优化方式的好处也很明显,只需要向上找一次就可以知道某个元素属于哪个集合

实现上,我们可以在查找操作的过程中,把对于 非根节点 把它 指向 它所在集合的根节点

int find(int x) {
    // 路径压缩
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

维护额外信息

考虑这样一个问题:求某个集合的节点数量应该怎么办?

只需要多开一个数组size[]来记录每个集合中的节点数量

初始化size[],每个集合只有一个节点,既,根节点自己。只有集合合并的时候才会影响到一个集合的节点数量。所以在合并的时候,我们只要把两个集合的节点数量加一起就可以了

比如:p[x]=y该操作将x合并到集合y中,那么显然集合数量的变化就是size[y] += size[x]

Code

我们把上面分析的所有代码总结一下,就可以完成本题。

#include <iostream>
#include <cstring>

using namespace std;

const int N = 100010;
int n, m;
int p[N], size[N];

// 查找
int find(int x) {
    // 路径优化
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

// 合并
int merge(int a, int b) {
    int x = find(a), y = find(b);
    p[x] = y;
    size[y] += size[x];
}

int main() {
    cin >> n >> m;
    // 初始化
    for (int i = 1; i <= n; i ++ ) p[i] = i, size[i] = 1;
    while (m -- ) {
        char t;
        int a, b;
        cin >> t >> a >> b;
        if (t == 'M') merge(a, b);
        else {
            int x = find(a), y = find(b);
            if (x != y) puts("No");
            else puts("Yes");
        }
    }
    return 0;
}

END

分类:

后端

标签:

数据结构与算法

作者介绍

小指针
V1