并查集萌新的疑惑
  • 板块P2078 朋友
  • 楼主mLazy
  • 当前回复2
  • 已保存回复2
  • 发布时间2024/7/24 13:07
  • 上次更新2024/7/24 14:39:03
查看原帖
并查集萌新的疑惑
517691
mLazy楼主2024/7/24 13:07

下面是我的代码,本人已 AC,但是我很疑惑——

#include <bits/stdc++.h>
using namespace std;

short A[10001],B[10001];
short rkA[10001],rkB[10001];
short s[10001];
short top=0;

//查询X所属的集合
short find(short* a,short X)
{
	short xr;
	for(xr=a[X];a[xr]!=xr;xr=a[xr])s[top++]=xr;
	while(top)
	{
		a[s[--top]]=xr;
	}
	return xr;
}

int main()
{
	//freopen("P2078_2.in","r",stdin);
	short N,M,P,Q,X,Y;
	cin>>N>>M>>P>>Q;
	//初始化
	for(short i=1;i<=N;i++)
	{
		A[i]=i;
		rkA[i]=1;
	}
	for(short i=1;i<=M;i++)
	{
		B[i]=i;
		rkB[i]=1;
	}
	//录入关系
	short xr,yr;
	for(short i=0;i<P;i++)
	{
		cin>>X>>Y;
		if(X==Y)continue;
		xr=find(A,X);
		yr=find(A,Y);
		
		if(rkA[yr]>rkA[xr])swap(xr,yr);
		rkA[xr]+=rkA[yr];
		A[yr]=xr;
	}
	for(short i=0;i<Q;i++)
	{
		cin>>X>>Y;
		if(X==Y)continue;
		//注意:X,Y<0
		xr=find(B,-X);
		yr=find(B,-Y);
		
		if(rkB[yr]>rkB[xr])swap(xr,yr);
		rkB[xr]+=rkB[yr];
		B[yr]=xr;
	}
  	//我把输出部分改成了下面的样子才AC
	short a=0,b=0;
	for(short i=1;i<=N;i++)if(find(A,i)==find(A,1))a++;
	for(short i=1;i<=M;i++)if(find(B,i)==find(B,1))b++;
	cout<<min(a,b)<<endl;
	return 0;
}

其中 rkA,rkB 用于按秩合并,分别对应 A、B 公司的员工。我想令其等于子节点的个数。

我尝试直接输出 min(rkA[find(A,1)],rkB[find(B,1)]),却得到了错误的结果(30pts)。为什么?是我按秩合并的代码写错了吗。

求大佬指点!必点关注!

2024/7/24 13:07
加载中...