关于并查集按秩合并导致RE,求助
查看原帖
关于并查集按秩合并导致RE,求助
490694
Compound_Interest楼主2022/8/14 11:16
#include<cstdio>
#define int long long
using namespace std;
const int maxn=5e6+10;
int fa[maxn],r[maxn],n,m,e,q,ans[maxn],siz[maxn];
bool vis[maxn];
struct node{
	int x,y;
}a[maxn],que[maxn];
int find(int x){
	if(fa[x]==x) return x;
	return fa[x]=find(fa[x]);
}
void Union(int x,int y){
	x=find(x),y=find(y);
	if(x==y) return;
	if(r[x]>r[y]) fa[y]=x,siz[x]+=siz[y];
	if(r[x]<r[y]) fa[x]=y,siz[y]+=siz[x];
	else r[y]++,fa[x]=y,siz[y]+=siz[x];//这里把r[y]++去掉RE->WA
}
signed main(){
	scanf("%lld%lld%lld",&n,&m,&e);
	for(int i=0;i<=n+m;i++) fa[i]=i,siz[i]=1;
	for(int i=1;i<=e;i++) scanf("%lld%lld",&a[i].x,&a[i].y);
	scanf("%lld",&q);
	for(int i=1;i<=q;i++){
		int t;scanf("%lld",&t);
		vis[t]=1;que[i]=a[t];
	}
	for(int i=n+1;i<=n+m;i++) Union(i,0);
	for(int i=1;i<=e;i++) 
		if(!vis[i]) Union(a[i].x,a[i].y);
	ans[q]=siz[0]-m-1;
	for(int i=q;i>=1;i--){
		Union(que[i].x,que[i].y);
		ans[i-1]=siz[0]-m-1;
	}
	for(int i=1;i<=q;i++) printf("%lld\n",ans[i]);
	return 0;
}

请问各位神犇这是什么原因

2022/8/14 11:16
加载中...