Biu
并查集支持的最基本操作：
将两个集合合并询问两个元素是否在一个集合当中并查集优化的两个操作：
路径压缩：当寻找一个元素的树根节点时，一旦找到，就将这条路径下的所有节点的父节点全部修改为树根节点，优化后几乎实现了接近 O(1) 的时间复杂度查找。按秩合并：一个不重要的优化操作，很少用到，主要是在合并的时候，将树高度较低的集合插到树高度教高的集合中(貌似是这样，没过多了解，没实现过)板子实现了路径压缩，就一行代码，递归寻找，回溯的时候就能实现路径压缩。
代码：
#include <iostream> using namespace std; const int N = 1e5+5; int n, m; int p[N]; // 存储每个元素的父节点是谁，初始化时每个元素单独一个集合，即为自己,p[x]=x // 返回x的祖宗节点+路径压缩 int find(int x) { if (p[x] != x) p[x] = find(p[x]); // 如果p[x]不是树根节点，则让p[x]等于它的树根节点 return p[x]; } int main() { cin >> n >> m; for (int i = 1; i <= n; ++i) p[i] = i; // 初始化，每个元素单独一个集合，为树根 while (m --) { char op[2]; int a, b; cin >> op >> a >> b; if (op[0] == 'M') p[find(a)] = find(b); else { if (find(a) == find(b)) puts("Yes"); else puts("No"); } } return 0; }