题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3018 题意：给你n个点，m条边，问你几笔能画完所有边 解析：首先这个图不连通，所以要分成几块来计算，每一块都有三种情况，如果是个欧拉图，那就一笔画玩，如果是孤立点那就不管，如果是其他的，那就输有几个度数为奇数的点，奇点/2就是总笔画数，所以ans = 奇点/2+欧拉图个数
#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> #include <vector> using namespace std; const int maxn = 1e5+100; int fa[maxn],odd[maxn]; int du[maxn],vis[maxn]; vector<int>tmp; void init(int n) { memset(odd,0,sizeof(odd)); memset(vis,0,sizeof(vis)); memset(du,0,sizeof(du)); for(int i=0;i<=n;i++) fa[i] = i; tmp.clear(); } int getFa(int x) { if(x==fa[x]) return x; return fa[x] = getFa(fa[x]); } void merge(int u,int v) { int t1 = getFa(u); int t2 = getFa(v); if(t1!=t2) fa[t1] = t2; } int main(void) { int n,m; while(~scanf("%d %d",&n,&m)) { init(n); for(int i=0;i<m;i++) { int u,v; scanf("%d %d",&u,&v); merge(u,v); du[u]++,du[v]++; } for(int i=1;i<=n;i++) { int fa = getFa(i); if(!vis[fa]) { vis[fa] = 1; tmp.push_back(fa); } if(du[i]%2) odd[fa]++; } int ans = 0; for(unsigned i = 0;i<tmp.size();i++) { if(du[tmp[i]]==0) continue; if(odd[tmp[i]]==0) ans++; else ans += odd[tmp[i]]/2; } printf("%d\n",ans); } return 0; }