一、并查集用来解决什么问题？
合并两个集合
判断两个元素是不是在同一个集合中
二、基本原理
每个集合用一棵树来表示。树根的编号就是整个集合的编号。每个节点存储它的父节点，p[x]表示x的父节点。
三、逻辑问题
-
如何判断树根
if (p[x] == x)
对于树根来说，它的父节点就是它本身
-
如何求x的集合编号
while (p[x] != x) x = p[x]
因为树根的编号就是整个集合的编号，所以找集合编号，就是找对应树根的编号
如果当前元素不是树根，那么就让当前元素的父节点作为当前元素，一直递归下去
-
如何合并两个集合：px是x的集合编号，py是y的集合编号
p[x] = y
只要让x的父节点指向y即可完成合并
四、优化
在求x的集合编号的过程中，如果x不是树根，那么会沿着父亲一直向上找，直至找到树根，这样就形成了一条从x到达树根的链条
这个时候，我们可以将这个链条上的所有元素的父节点都指向根节点，因为我们需要的是元素的根节点，而不是父节点
这个方法也叫做路径压缩
五、案例
一共有 n 个数，编号是 1∼n，最开始每个数各自在一个集合中。
现在要进行 mm 个操作，操作共有两种：
-
M a b，将编号为 aa 和 bb 的两个数所在的集合合并，如果两个数已经在同一个集合中，则忽略这个操作； -
Q a b，询问编号为 aa 和 bb 的两个数是否在同一个集合中；
输入格式
第一行输入整数 n 和 m。
接下来 mm 行，每行包含一个操作指令，指令为 M a b 或 Q a b 中的一种。
输出格式
对于每个询问指令 Q a b，都要输出一个结果，如果 aa 和 bb 在同一集合内，则输出 Yes，否则输出 No。
每个结果占一行。
数据范围
1≤n,m≤105
输入样例：
4 5
M 1 2
M 3 4
Q 1 2
Q 1 3
Q 3 4
输出样例：
Yes
No
Yes
代码如下：
#include <iostream>
using namespace std;
const int N = 100010;
int p[N];//用来存放x的父节点
int n, m;
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(find(a) == find(b)) puts("Yes");
else puts("No");
}
}
return 0;
}
