AcWing 836. 合并集合
原题链接
简单
作者:
acwing_陌路
,
2021-08-20 18:11:53
,
所有人可见
,
阅读 225
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
int p[N];
int find(int x)//返回x的祖宗节点 + 路径压缩
{
if(p[x] != x) p[x] = find(p[x]);//x的爸爸直接等于其祖宗
return p[x];
}
int main()
{
int n,m;
cin >> n >> m;
for(int i = 1;i <= n;i++) p[i] = i;//初始时,每个人的父节点等于自己
while(m --)
{
char op;
cin >> op;
int a,b;
cin >> a >> b;
if(op == 'M') p[find(a)] = find(b);//让a的祖宗的爸爸等于b的祖宗
else
{
if(find(a) == find(b)) puts("Yes");//如果他俩祖宗一样,说明在一个集合里
else puts("No");
}
}
return 0;
}