题目描述
模板题:并查集
C++代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, m, p[N];
// 查找x的祖宗结点 + 路径压缩
int find(int x){
if(p[x] != x) //不是根结点
p[x] = find(p[x]);
return p[x];
}
int main(){
char op[2];
int a, b;
cin >> n >> m;
for(int i = 1; i <= n; i++)
p[i] = i;
while(m--){
scanf("%s%d%d", op, &a, &b);
if(op[0] == 'M'){
p[find(a)] = find(b);
}
else{
if(find(a) == find(b))
cout << "YES" << endl;
else
cout << "NO" << endl;
}
}
return 0;
}