下面是我的代码,本人已 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)。为什么?是我按秩合并的代码写错了吗。
求大佬指点!必点关注!