为什么拓展域并查集换一下合并方向就不对了呀?
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(){
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);
}
}
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分了?