传送
这个题我们需要一个大胆的想法（虽然AC后看了题解知道这是个定理）
（求证明qwq）
如果一个图有2或0个奇点，它就一定可以一笔画出，如果不是2或0个奇点，那答案就是奇点数/2
（私认为因为两个奇点确定一条边，所以答案是奇点数/2）
代码就出来了：
#include<iostream> #include<cstdio> #include<cmath> #include<cstring> using namespace std; int n,m,bian[10001][10001],x,y,js[1001]; int main() { int jjs=0; scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) {scanf("%d%d",&x,&y); bian[x][y]=1; bian[y][x]=1; js[x]++; js[y]++; } for(int i=1;i<=n;i++) {if(js[i]%2==1)jjs++; //printf("js[%d]=%d\n",i,js[i]); } if(jjs==2||jjs==0) {printf("1\n");return 0; } int ans=jjs/2; printf("%d",ans); }
转载于:https://www.cnblogs.com/lcez56jsy/p/10726170.html
