作用:
1.将两个集合合并
2.询问两个元素是否在一个集合当中
基本原理:
每个集合用一棵树来表示,树根的编号就是整个集合的编号。每个节点存储它的父节点,p[x]表示x的父节点
操作:
1.判断树根:
if(p[x]==x);
2.求x的集合编号:
while(p[x]!=x) x=p[x];
3.如何合并两个集合:
p[x]是x的集合编号,py是y的集合编号。p[x]=y;
优化:
路径压缩~o(1);
AC代码:
#include <iostream>
using namespace std;
const int N=1e5+10;
int a,b;
char op[2];//操作
int n,m;
int p[N];//存储父节点
int find(int x)//返回节点祖宗
{
if(p[x]!=x) p[x]=find(p[x]);
return p[x];
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++) p[i]=i;//初始化每一个节点是一个集合 所以自己就是祖宗
while(m--)
{
cin>>op>>a>>b;
if(op[0]=='M') p[find(a)]=find(b);//让编号a的集合 认集合b祖宗当爹
else
{
if(find(a)==find(b)) cout<<"Yes"<<endl;//两集合祖宗相等
else cout<<"No"<<endl;
}
}
return 0;
}
标签:int,查集,find,编号,集合,节点,op
From: https://www.cnblogs.com/Eric0521/p/18030447