此题为并查集最最最裸的模板题。
两个并查集的核心操作: 1 ·将两个集合合并。 2·询问两个元素是否在一个集合当中。
基本原理:每个集合用一颗树表示,树根的编号就是整个树所有节点编号,每个节点存储他的父亲节点,p[x]表示x的父节点,若p[x]= x,则x 为根节点。
三个核心要点:
1,怎样判断树根 p[x]==x;
2,如何求集合编号 while(p[x]!=x)x=p[x];
3,如何合并两个集合:find(x)是x的集合编号 find(y)是y的集合编号,p[find(x)]=find(y)即可。
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
#include<iostream>
using namespace std;
const int N = 100010;
int p[N];
//并查集,find为并查集核心操作,以递归法遍历到根节点。
int find(int 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=='M')p[find(a)]=find(b);
else{
if(find(a)==find(b))puts("Yes");
else puts("No");
}
}
return 0;
}