萌新发问
查看原帖
萌新发问
320449
forest114514楼主2023/8/29 21:17

为什么拓展域并查集换一下合并方向就不对了呀?

WA 0pts的代码

//蒟蒻一枚
#include<bits/stdc++.h>
#define re register
#define il inline
using namespace std;
typedef long long LL;
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch&15),ch=getchar();
	return x*f;
}
const int N=1005;
int n,m,f[N*2]={0},ans=0;
int p,q;
il int getf(int x){
	return (f[x]==x)?x:f[x]=getf(f[x]);
}
il void merge(int a,int b){
	int fa=getf(a),fb=getf(b);
	if(fa!=fb)
	f[fa]=fb;
}
int  main(){
	//ios::sync_with_stdio(false);
	//cin.tie(0);cout.tie(0);
	n=read();
	for(int i=1;i<=n*2;++i) f[i]=i;
	m=read();
	char opt;
	for(int i=1;i<=m;++i){
		cin>>opt;
		p=read();q=read();
		
		if(opt=='E'){
			merge(p,q+n);
			merge(q,p+n);
		}
		else{
			merge(p,q);
//			merge(p+n,q+n);
		}
	}
	for(int i=1;i<=n;++i) if(f[i]==i) ans++;
	cout<<ans<<'\n';
	return 0;
}

AC的代码

//蒟蒻一枚
#include<bits/stdc++.h>
#define re register
#define il inline
using namespace std;
typedef long long LL;
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch&15),ch=getchar();
	return x*f;
}
const int N=1005;
int n,m,f[N*2]={0},ans=0;
int p,q;
il int getf(int x){
	return (f[x]==x)?x:f[x]=getf(f[x]);
}
il void merge(int a,int b){
	int fa=getf(a),fb=getf(b);
	if(fa!=fb)
	f[fa]=fb;
}
int  main(){
	//ios::sync_with_stdio(false);
	//cin.tie(0);cout.tie(0);
	n=read();
	for(int i=1;i<=n*2;++i) f[i]=i;
	m=read();
	char opt;
	for(int i=1;i<=m;++i){
		cin>>opt;
		p=read();q=read();
		
		if(opt=='E'){
			merge(p+n,q);
			merge(q+n,p);
		}
		else{
			merge(p,q);
//			merge(p+n,q+n);
		}
	}
	for(int i=1;i<=n;++i) if(f[i]==i) ans++;
	cout<<ans<<'\n';
	return 0;
}

其中只把merge(p+n,q);和merge(q+n,p);换成了merge(p,q+n);merge(q,p+n);为什么就0分了?

2023/8/29 21:17
加载中...