考虑这个图:【□□】,显然其对应数据为 8 8 1 2 2 3 3 4 4 1 5 6 6 7 7 8 8 1,没有一个奇点,然而由于两个“□”没有连接,所以输出应为2。但按题解输出为1。这个错误出现在测试点6-11。
//这是54分代码qwq
#include<bits/stdc++.h>
using namespace std;
bool mapo[1000][1000];
bool mapin[1000][1000];
int mapl[1000],mapc=0;
bool mapflod[1000];
int n,m,floded=0;
void flod(int fr){
mapflod[fr]=true;
mapin[mapc][fr]=true;
floded+=1;
for(int i=1;i<=n;i++){
if(mapo[fr][i]==true and mapflod[i]==false) flod(i);
}
}
int req=0;
int main(){
cin>>n>>m;
int a,b;
for(int i=1;i<=m;i++){
cin>>a>>b;
mapo[a][b]=true;
mapo[b][a]=true;
mapl[a]+=1;
mapl[b]+=1;
}
for(int i=1;i<=n;i++){
if(mapl[i]==0) continue;
else if(mapflod[i]==false){
mapc+=1;
flod(i);
}
if(floded==n) break;
}
req+=mapc;
for(int i=1;i<=mapc;i++){
int jic=0;
for(int j=1;j<=n;j++){
if(mapin[i][j] and mapl[j]%2!=0) jic++;
}
if(jic>2) req+=(jic-2)/2;
}
cout<<req;
}