此题考查以一笔画知识延伸出得欧拉(半)图问题，具体解决方法：
1、如果不考虑连通性的话，因为此题的背景为无向图，因此只需判断奇点数量，当奇点数量为0/2时，可以直接输出1，否则ans=奇点数量/2
代码如下：
#include<bits/stdc++.h>//万能头文件大法好 using namespace std; int a[10001]; int n,m,ans; int main() { cin>>n>>m; for(int i=1;i<=m;i++) { int x,y; cin>>x>>y; a[x]++; a[y]++; } for(int i=1;i<=n;i++) { if(a[i]%2==1) ans++; } if(ans) cout<<ans/2; else cout<<ans+1; return 0; }
2、如果考虑图存在不连通的可能，就需要并查集维护。
显然此题并没有说明数据情况，按理来说是要按照此种方式处理的，但是评测出现了错误，暂且认为是数据问题
代码如下：
#include<bits/stdc++.h> using namespace std; int n,m,a,b,fa[1010],cnt[1010]={0},ans=0; bool dg[1010],visit[1010]; long long read()//快读 { long long ans=0; char ch=getchar(),last=' '; while(ch<'0'||ch>'9') {last=ch;ch=getchar();} while(ch>='0'&&ch<='9') {ans=ans*10+ch-'0';ch=getchar();} if(last=='-')ans=-ans; return ans; } int get(int k)//寻找根节点 { if(fa[k]==k)return k; else return fa[k]=get(fa[k]); } void Union(int x,int y)//合并 { fa[get(x)]=get(y); } int main() { n=read();m=read(); for(int i=1;i<=n;i++) fa[i]=i; for(int i=1;i<=m;i++){ a=read();b=read(); dg[a]=!dg[a];dg[b]=!dg[b]; //真为奇数，假为偶数 visit[a]=true; visit[b]=true; //访问过标记为true if(get(a)!=get(b))Union(a,b); //如果不在一个集合就合并 } for(int i=1;i<=n;i++){ if(dg[i])cnt[get(i)]++; //统计每个点所在的图共有几个度数为奇数的 } for(int i=1;i<=n;i++){ if(get(i)==i&&visit[i]){ //如果是根节点同时已经被访问过 if(cnt[i]>0)ans+=cnt[i]>>1; //加上该图的答案 else ans++; //否则该图可以一笔画，答案加1 } } cout<<ans; return 0; }
另外总结欧拉图相关知识如下：
存在欧拉回路的图为欧拉图，如果仅存在欧拉通路（即：一笔画完成后不能回到起点，无法构成回路），为欧拉半图。
平凡图：一个点构成的图
无向图G是欧拉图当且仅当G是连通图，且G中没有奇度顶点。
无向图G是半欧拉图当且仅当G是连通的，且G中恰有0或2个奇度顶点，一个为起点，一个为终点
有向图D是欧拉图当且仅当D是强连通的且每个顶点的入度都等于出度。
有向图D是半欧拉图当且仅当D是单向连通的，且D中恰有2个奇度顶点，其中一个的入度比出度大1，另一个的出度比入度大1，而其余顶点的入度都等于出度。