题目描述
裸的并查集:
1. 合并两个集合
2. 判断两个元素是否在同一个集合中
核心:
find() 操作 —> 找每个节点的根节点并进行路径压缩操作
样例
输入样例:
4 5
M 1 2
M 3 4
Q 1 2
Q 1 3
Q 3 4
输出样例:
Yes
No
Yes
算法1
(合并) $O(n)$
(查询) $O(1)$
C++ 代码
#include <iostream>
#include <cstring>
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]); //找到x的根节点,找到这个数是属于哪个集合的
return p[x];
}
int main()
{
scanf("%d %d",&n,&m);
for(int i = 1; i <= n; i ++) p[i] = i; // 初始时, 每个点的父节点都是自己
while(m --)
{
string op;
int a, b;
cin >> op >> a >> b; //scanf读字符的话会莫名其妙的加上空格或者回车的字符,若读字符串的话不会出现这种情况
//若要用scanf进行字符输入,最好定义成字符数组,用的时候直接取op[0];
if(op == "M") p[find(a)] = find(b); //并查集的集合合并操作,将a那一块当成b这一块的子树
else //查询两个元素是否在一个集合里
{
if(find(a) == find(b)) //第一次执行这一步时,亦是路径压缩的过程(回溯过程中会将每个点直接指向根节点)
puts("Yes");
else puts("No");
}
}
return 0;
}