AcWing 836. 合并集合
【题目描述】

在查看解析之前，先给自己一点时间思考哦！

【题解】
并查集是一种用于处理集合合并与查询问题的数据结构，通常支持以下两种操作：
Find：查询一个元素所在的集合。
Union：将两个元素所在的集合合并为一个集合。

为了提高效率，常用以下优化：
路径压缩：在find操作时，将访问路径上的每个节点直接指向根节点，从而加速后续查询。
【参考代码】

#include <iostream>
using namespace std;const int N = 1e5 + 10;  // 最大集合数为 10^5
int p[N];  // 用于存储每个元素的父节点
int n, m;  // n 为集合数，m 为操作数// 查找操作：返回元素 x 所在集合的根
int find(int x) {if(p[x] != x)  // 如果 p[x] 不是 x，说明 x 不是根节点p[x] = find(p[x]);  // 路径压缩，将 x 直接指向根节点return p[x];  // 返回根节点
}int main() {cin >> n >> m;  for(int i = 1; i <= n; i++)  // 初始化时，每个元素自成一组p[i] = i;while(m--) { string op;  int a, b;  cin >> op >> a >> b;if(op == "M")  // 如果是 M 操作，合并 a 和 b 所在的集合p[find(a)] = find(b);  // 将 a 和 b 合并else {  // 如果是 Q 操作，查询 a 和 b 是否在同一个集合if(find(a) == find(b))  // 如果 a 和 b 的根节点相同，则在同一个集合cout << "Yes" << endl;elsecout << "No" << endl;  // 否则不在同一个集合}}return 0;
}