这是原本 AC 的代码:
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 1010;
const ll M = 5010;
#define aginst(x) (x+n)
ll fa[N<<1],siz[N<<1];
ll n,m;
ll GetLL(){
ll x = 0,h = 1;
char ch = getchar();
while(!(('0'<=ch&&ch<='9')||ch=='-')) ch = getchar();
if(ch=='-') h = -1;
else x = ch-'0';
ch = getchar();
while('0'<=ch&&ch<='9'){
x = x*10+ch-'0';
ch = getchar();
}
return x*h;
}
char GetC(){
char ch = getchar();
while(!('A'<=ch&&ch<='Z')) ch = getchar();
return ch;
}
void init(){
for(ll i = 1; i <= n<<1; i++) fa[i] = i;
for(ll i = 1; i <= n; i++) siz[i] = 1;
for(ll i = 1; i <= n; i++) siz[i+n] = 1;
}
ll findf(ll x){
if(fa[x]==x) return x;
return fa[x] = findf(fa[x]);
}
void merge(ll x,ll y){
ll fx = findf(x),fy = findf(y);
if(fx==fy) return;
if(siz[fx]<siz[fy]){//注意这一行
siz[fy]+=siz[fx];
fa[fx] = fy;
//printf("%lld->%lld\n",fx,fy);
} else {
siz[fx]+=siz[fy];
fa[fy] = fx;
//printf("%lld->%lld\n",fy,fx);
}
}
int main(){
n = GetLL();m = GetLL();
init();
while(m--){
char op;
ll p,q;
op = GetC();p = GetLL();q = GetLL();
if(op=='F'){
merge(p,q);
} else {
merge(p,aginst(q));
merge(q,aginst(p));
}
}
ll res = 0;
for(ll i = 1; i <= n; i++) if(findf(i)==i) res++;
printf("%lld",res);
return 0;
}
```
将有标记的一行改成这样
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 1010;
const ll M = 5010;
#define aginst(x) (x+n)
ll fa[N<<1],siz[N<<1];
ll n,m;
ll GetLL(){
ll x = 0,h = 1;
char ch = getchar();
while(!(('0'<=ch&&ch<='9')||ch=='-')) ch = getchar();
if(ch=='-') h = -1;
else x = ch-'0';
ch = getchar();
while('0'<=ch&&ch<='9'){
x = x*10+ch-'0';
ch = getchar();
}
return x*h;
}
char GetC(){
char ch = getchar();
while(!('A'<=ch&&ch<='Z')) ch = getchar();
return ch;
}
void init(){
for(ll i = 1; i <= n<<1; i++) fa[i] = i;
for(ll i = 1; i <= n; i++) siz[i] = 1;
for(ll i = 1; i <= n; i++) siz[i+n] = 1;
}
ll findf(ll x){
if(fa[x]==x) return x;
return fa[x] = findf(fa[x]);
}
void merge(ll x,ll y){
ll fx = findf(x),fy = findf(y);
if(fx==fy) return;
if(siz[fx]<=siz[fy]){
siz[fy]+=siz[fx];
fa[fx] = fy;
//printf("%lld->%lld\n",fx,fy);
} else {
siz[fx]+=siz[fy];
fa[fy] = fx;
//printf("%lld->%lld\n",fy,fx);
}
}
int main(){
n = GetLL();m = GetLL();
init();
while(m--){
char op;
ll p,q;
op = GetC();p = GetLL();q = GetLL();
if(op=='F'){
merge(p,q);
} else {
merge(p,aginst(q));
merge(q,aginst(p));
}
}
ll res = 0;
for(ll i = 1; i <= n; i++) if(findf(i)==i) res++;
printf("%lld",res);
return 0;
}
```
再输入举得反例:
```
4 3
E 1 2
F 1 3
F 1 4
```
输出 `0`,错误
by yyz1005 @ 2023-03-29 13:04:22
感觉应该是合并顺序的问题
by yyz1005 @ 2023-03-29 13:06:29
合并顺序的问题,1到n总是作为父节点的
by 1001a @ 2023-04-02 20:18:42