合并集合
题目 合并集合
思路分析
用一个数组去记录各点的祖宗结点是什么 下标标识各个点本身
一开始 所有点都是独立的 就把各下标对应的father都设为本身
要使某点从属入某集合 就直接在该点的fa[]存放另一结点
当然 优化时做了 数组中不记录直接父节点 而是记录祖宗结点
所以在进行合并操作时 要先进行find操作 找到祖宗结点
再把祖宗结点插入到另一个集合的祖宗结点下 实现合并
fa[find(a)]=find(b); 而判断两个结点是否从属一个集合
要做的就是比较一下祖宗结点是否相等
if(find(a)==find(b))
显然核心就在于这个find()
//返回x所在集合的编号（祖宗结点）
int find(int x) {
if(fa[x]!=x)
fa[x]=find(fa[x]);//路径压缩优化
return fa[x];
}
递归的过程中 让直接存上祖宗结点
代码实现
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int fa[N];
//返回x所在集合的编号（祖宗结点）
int find(int x)
{
if(fa[x]!=x)
fa[x]=find(fa[x]);//路径压缩优化
return fa[x];
}
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
fa[i]=i;//初始化 让父节点指向自己
}
while(m--)
{
char op[2];
int a,b;
cin>>op>>a>>b;
if(op[0]=='M')
{
fa[find(a)]=find(b);//让a的祖宗结点等于b的祖宗结点 把a插在b里面
}
else
{
if(find(a)==find(b))
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
}
}
return 0;
}
💬 评论