AcWing 836. 合并集合
原题链接
简单
作者:
no_one
,
2022-08-07 17:39:13
,
所有人可见
,
阅读 151
并查集
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 100010;
int q[N];
int n, m;
int find(int i)
{
if(q[i] != i) q[i] = find(q[i]); // 找到祖宗节点。
return q[i]; // 返回祖宗节点。
}
int main()
{
cin.tie(0);
cin >> n >> m;
for(int i = 0; i < n; i ++) q[i] = i;
while(m --)
{
int x, y;
char op[2];
scanf("%s%d%d", op, &x ,&y);
if(op[0] == 'M')
{
q[find(x)] = find(y); // 将两个集合的祖宗节点连接起来。
}
else
{
if(find(x) == find(y)) puts("Yes"); // 如果两个数的祖宗节点相同 那就是在一个集合里面
else puts("No");
}
}
return 0;
}