并查集 : 又称祖宗去哪儿了
并查集 : 将两个集合合并,查询两个元素是否在一个集合中
#include<iostream>
using namespace std;
const int N=1e5+10;
int p[N];
int find(int x) //寻找祖宗
{
if (p[x]!=x) p[x]=find(p[x]); //一直往上找
return p[x]; //返回找到的祖宗
}
int main()
{
int n,m;
cin>>n>>m;
for (int i=0;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)) printf("Yes\n");
else printf("No\n");
}
return 0;
}