AcWing 836. 合并集合
原题链接
简单
作者:
咸鱼堆上的猫
,
2024-04-11 21:22:20
,
所有人可见
,
阅读 2
#include<iostream>
using namespace std;
const int N = 100010;
int p[N];
//原理:每个集合用一棵树表示,树根的编号就是整个集合的编号,每个节点存储他的//父节点 p[x]表示x的父节点 find(x)表示x的树根
//那么p[find(x)]表示 p树根的父节点 那么find(p[x])表示x父节点的树根
//注意区别树根和父节点
int find(int x)//求x的集合编号 求树根 如果树根(编号)一样则在一个集合里
{
if(p[x]!=x) //如果x不是p[x]的父节点,只有树根p[x]=x,如果x不是树根
p[x]=find(p[x]);
return p[x];//如果p[x]==x即为树根则返回p[x],也是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);//一个集合的根节点的父结点连到另个s集合 //将x树作为子树给y的树根
//x树根的父节点 等于 y的树根
else
{
if(find(a) ==find(b)) puts("Yes");//树根相同
else puts("No");
}
}
return 0;
}