题目描述

关系

内容

一共有 $n$ 个数，编号是 $1\sim n$，最开始每个数各自在一个集合中。

现在要进行 $m$ 个操作，操作共有两种：

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

输入格式

第一行输入整数 $n$ 和 $m$。

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

输出格式

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

每个结果占一行。

数据范围

$1\le n,m\le {10}^5$

输入样例：

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

输出样例：

Yes
No
Yes

问题分析

最初思路

思路分析

对于一棵树，根节点具有唯一性，所以可以用根节点代表一个集合。

合并集合，就让另一个集合的根节点指向另一个树的根节点就行了。

并查集有两个优化：

1. 遍历过程中让每个节点都直接指向根节点；（路径压缩）
2. 我们更倾向于在合并时，将矮树合并到高树中（按秩合并-启发式合并）；

执行流程设计

总结

代码实现

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
int n, m;
int p[N]; // p[i] = j => i 节点的父亲是j, 路径压缩后, p[i] 表示当前集合的根节点
int r[N]; // r[i] = k => i 集合的高度为k

int find(int x) {
    // 如果还没有找到根节点, 就一直递归往上找
    if (p[x] != x) {
        // 路径压缩
        p[x] = find(p[x]); 
    }
    return p[x];
}

void merge(int a, int b) {
    // 找到 a, b 所在集合的代表元素
    a = find(a), b = find(b);
    
    // 同一个集合就不用合并
    if (a == b) return;
    
    if (r[a] > r[b]) p[b] = a; // 将小树b合并到a上
    else {
        p[a] = b;
        if (r[a] == r[b]) r[b]++; // 两棵树高度相同的时候, b 树的高度应该 + 1
    }
    
}

int main()
{
    cin >> n >> m;
    // 并查集初始化
    for (int i = 1; i <= n; i++) {
        // 初始每个集合的高度为1, 父节点指向自己.
        p[i] = i;
        r[i] = 1; 
    }
    
    while (m--) {
        char op;
        int a, b;
        cin >> op >> a >> b;
        if (op == 'Q') {
            if (find(a) == find(b)) puts("Yes");
            else puts("No");
        } else { // 合并两个集合
            merge(a, b);            
        }
    }
    return 0;
}