思路:主要在find函数,路径压缩和合并合二为一
具体见图:
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int n, m, c[N];
int find(int x)
{
if(c[x] != x) c[x] = find(c[x]);
return c[x];
}
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i ++ ) c[i] = i;
char op;
while(m -- )
{
int a, b;
cin >> op;
if(op == 'M') cin >> a >> b, c[find(a)] = find(b);
if(op == 'Q')
{
cin >> a >> b;
if(find(a) == find(b)) cout << "Yes";
else cout << "No";
puts("");
}
}
return 0;
}