题目大意
实现两个操作:快速地合并集合;查询两元素是否在同一集合
解题思路
运用最基础的并查集即可
具体代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m;
int p[N];
int find(int x) //返回x所在的集合的编号
{
if(p[x]!=x) p[x]=find(p[x]); //路径压缩
return p[x];
}
void merge(int a,int b) //将a和b所在的集合合并
{
p[find(a)]=find(b);
}
int main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++) //初始化并查集
p[i]=i;
while(m--)
{
char op;
int a,b;
cin>>op>>a>>b;
if(op=='M')
{
if(find(a)==find(b)) continue; //两者已经在同一集合,忽略即可
merge(a,b);
}
else
{
if(find(a)==find(b)) cout<<"Yes"<<'\n';
else cout<<"No"<<'\n';
}
}
return 0;
}