题外：突然想起前两天百度暑期实习笔试第二题(n个比赛选手最开始均匀分配到n个准备区，之后有两种操作，一种是将两个准备区的选手合并到一个准备区，关闭其中一个准备区；第二种是查询两个选手当前所在准备区编号的距离)应该是考察并查集的，tmd又想了想这不就是裸题吗。。。当时没复习到完全没想到这茬儿，自己在那构造半天调试没通过
- 并查集可以应用的场景：
- 快速地将两个集合合并
- 询问两个元素是否在一个集合当中
- 并查集可以在近乎O(1)的时间复杂度下实现上述两个操作
- 基本原理：每个集合用一棵树来表示，树根的编号就是整个集合的编号。每个节点存储它的父节点，p[x]表示x的父节点
- 需压考虑的问题：
- 问题1： 如何判断树根： if(p[x] == x)
- 问题2： 如何求x的集合编号： while（x != p[x]) x = p[x] || 朴素的思路复杂度较高，可以用__路径压缩__优化到接近O(1)
- 问题3： 如何合并两个集合：px是x集合的编号，py是y集合的编号。p[x] = y
#include <iostream>
using namespace std;
const int N = 100010;
int n, m;
int p[N];
//最核心的操作
int find(int x) { // 返回x的祖宗节点，内含了路径压缩
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
int main() {
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i ++ ) p[i] = i; // 初始时每个节点是自己的祖宗节点
while(m -- ) {
char op[2];
int a, b;
scanf("%s%d%d", op, &a, &b);
if(op[0] == 'M') p[find(a)] = find(b);
else if(op[0] == 'Q') {
if(find(a) == find(b)) puts("Yes");
else puts("No");
}
}
return 0;
}