***关于并查集的一个问题
  • 板块P1551 亲戚
  • 楼主zfznbnb
  • 当前回复4
  • 已保存回复4
  • 发布时间2022/5/22 20:11
  • 上次更新2023/10/28 00:49:20
查看原帖
***关于并查集的一个问题
608251
zfznbnb楼主2022/5/22 20:11
#include<cstdio>
#include<iostream>
using namespace std;
int n,m,p,x,y,fa[10009];
int find(int x) 
{
   if(fa[x]==x)return x;
   return fa[x]=find(fa[x]);
} 
void combine(int a,int b)
{
   fa[find(a)]=find(b);
}
int main()
{
   cin>>n>>m>>p;
   for(int i=1;i<=n;i++)
   {
   	fa[i]=i; 
   }
   for(int i=1;i<=m;i++)
   {
   	cin>>x>>y;
   	combine(x,y);
   }
   for(int i=1;i<=p;i++)
   {
   	cin>>x>>y;
   	if(find(x)==find(y))/*判断两人是否为亲戚(既然进行了路径压缩,为什么不写成if(fa[x]==fa[y])) */
   	{
   	{
   		cout<<"Yes"<<endl;
   	}
   		
   	else
   		cout<<"No"<<endl;
   }
   return 0;
}

如上,30行注释:既然进行了路径压缩,为什么不写成if(fa[x]==fa[y])

2022/5/22 20:11
加载中...