AcWing 836. 合并集合
原题链接
简单
作者:
跟着灿哥学切菜
,
2021-01-15 14:50:30
,
所有人可见
,
阅读 218
#include <iostream>
using namespace std;
const int N = 100010;
int p[N];
int find(int x) {
//找到x的所在的树的根节点
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
int main() {
int n, m;
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') {
//如果不在一个集合中, 两者进行合并, 否则, 不要进行合并。
if (find(a) != find(b)) p[find(a)] = find(b);
}
else {
if (find(a) == find(b)) puts("Yes");
else puts("No");
}
}
return 0;
}