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。现在有两个操作：

M（merge）。合并两个数到一个集合中，如M a b，则表示a和b合并到一个集合。
Q（query）。查询两个数是否在一个集合，如Q a b，查询a和b是否在一个集合当中。

题目分析

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

常规思路

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

使用并查集

概念

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

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

白色数字：父节点编号；
绿色数字：节点本身的编号；

在这里，我们需要明确「集合与节点是包含关系」。

「用集合的根节点编号表示一个集合」。比如，也就是初始化之后，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的最终根节点」。

根据「初始化的规则」，我们可以直观的知道，判断「一个点是不是最终根节点」，实际上就是在看「一个点的编号是否等于它的父节点的编号」。用代码表示就是(p[i] == i)。
经过合并之后，「节点的所属集合就会改变」。

如图中「节点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」