一、理解与感悟
最裸并查集
1、将两个集合合并。
2、询问两个元素是否在一个集合当中 ,近乎(O(1))时间内支持两个操作
基本原理:每个集合用一棵树来表示,树根的编号就是整个集合的编号,每个节点存储它的父节点,(p[x])表示(x)的父节点
-
如何判断树根?
if(p[x]==x)
-
如何求(x)的集合编号?
find(x)
-
如何合并两个集合?
p[find(a)] = find(b)
二、C++代码
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int n, m;
int p[N]; //爸爸数组
//递归查找父节点
int find(int x) {
if (p[x] != x) p[x] = find(p[x]); //这里的递归是带路径压缩的
return p[x];
}
int main() {
//优化输入
ios::sync_with_stdio(false);
cin >> n >> m;
//步骤1:初始化
for (int i = 1; i <= n; i++)p[i] = i;
while (m--) {
char op;
int a, b;
cin >> op >> a >> b;
//步骤2:通过p[find(a)]=find(b)合并并查集
if (op == 'M') p[find(a)] = find(b); //a的祖宗是b的祖宗的儿子,实现了两个集合的合并
else {
if (find(a) == find(b)) puts("Yes"); // 两个节点在一个集合里
else puts("No"); //不在一个集合里
}
}
return 0;
}