题面：
一共有 \(n\) 个数，编号是 \(1∼n\)，最开始每个数各自在一个集合中。
现在要进行 \(m\) 个操作，操作共有两种：
1、M a b，将编号为 \(a\) 和 \(b\) 的两个数所在的集合合并，如果两个数已经在同一个集合中，则忽略操作；
2、Q a b，询问编号为 \(a\) 和 \(b\) 的两个数是否在同一个集合中；
原题链接：836. 合并集合 - AcWing
并查集
对lareges大佬的笔记的再总结，自用学习，感谢大佬
原文非常清晰明了，膜拜：下班前几分钟，我彻底弄懂了并查集
- 并查集(Union Find)，也叫「不相交集合(Disjoint Set)」，
顾名思义，它专门用于动态处理不相交集合的「合并」与「查询」问题。 - 并查集的两种操作：
- 合并：合并两个元素所属集合；
- 查询：查询某个元素所属集合。这可以用于判断两个元素是否属于同一集合。
parent数组：p[i]表示编号为i的节点的父节点的编号。- 特别地，定义根节点的父节点是其自身。
- 代表元法：把每个集合看成一棵树，节点元素一一对应，根节点称为该集合的代表元。
- 树的根节点的编号为整个树（集合）的编号，
对于任一元素 \(x\)，可以自底向上追溯到根节点，来判断它属于哪个集合。 - 设计理念：三个不重要
- 谁作为根节点不重要：根节点与非根节点只是位置不同，并没有附加的含义；
- 树怎么形成的不重要：合并的时候任何一个集合的根节点指向另一个集合的根节点就可以；
- 树的形态不重要：理由同「谁作为根节点不重要」。
- 树的根节点的编号为整个树（集合）的编号，
p[]数组的初始化：- 根据代表元法，最初每个元素都是一棵树；
- 树中只有根节点，因此对于任一元素 \(i\) ，都有 \(p [ i ] = i\) 成立。
- 代码：
for (int i = 1; i <= n; i++) p[i] = i;
- 查询：追溯根节点，来判断节点属于哪个集合。
- 时间复杂度 \(O(n)\)：
while (p[x] != x) x = p[x];（\(n\) 为树的高度） - 优化方案：路径压缩
- 从元素 \(x\) 不断追溯到根节点会形成一条路径；
- 查询结束后，我们将该路径上除了根节点的每个节点都直接连接到根节点上；
- 在后续的查询过程中，若查询的是该路径上的点，时间复杂度即为 \(O(1)\) 。
- 时间复杂度 \(O(n)\)：
- 合并：将其中一棵树的根节点指向另一棵树的根节点，从而合并两棵树。
- 代码：
p[find(a)] = find(b);
- 代码：
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, m, a, b;
int p[N]; //p[x]: 指向x的父节点
char op;
//返回元素x所属集合的编号
int find(int x) {
if (p[x] != x) //如果元素x不是根节点
p[x] = find(p[x]); //让元素x直接指向根节点
return p[x]; //返回x的父节点的编号
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++) p[i] = i;
//法二：iota(p, p + n + 1, 0); //顺序赋值函数iota(起点，终点，起始值)
while (m--) {
cin >> op >> a >> b;
if (op == 'M')
p[find(a)] = find(b);
else
cout << (find(a) == find(b) ? "Yes\n" : "No\n");
}
}