题意：给你无向图的N个点和M条边,保证这M条边都不同且不会存在同一点的自环边,现在问你至少要几笔才能所有边都画一遍.(一笔画的时候笔不离开纸)
对于这个题，处理每个联通分量需要画几笔就好了
对于只有一个点的，0笔
是（半）欧拉图的，需要1笔
对于非（半）欧拉图的，需要该图中奇数度的点数目/2
链接：hdu 3018
#include <iostream> #include <algorithm> #include <cstdio> #include <cmath> #include <cstring> #include <string> #include <set> #include <map> #include <stack> #include <queue> using namespace std; const int maxn = 100005; const int maxm = 1000050; const int inf = 0x7f7f7f7f; int n, m; int fa[maxn]; int degree[maxn]; int num[maxn]; int sum[maxn]; int findset(int x) { if(fa[x] == -1) { return x; } return fa[x] = findset(fa[x]); } int main() { while(scanf("%d", &n) != EOF) { scanf("%d", &m); memset(degree, 0, sizeof(degree)); memset(fa, -1, sizeof(fa)); memset(num, 0, sizeof(num)); memset(sum, 0, sizeof(sum)); for(int i = 1; i <= m; i++) { int a, b; scanf("%d %d", &a, &b); degree[a]++; degree[b]++; a = findset(a); b = findset(b); if(a != b) { fa[a] = b; } } for(int i = 1; i <= n; i++) { num[findset(i)]++; if(degree[i] % 2) sum[findset(i)]++; } int ans = 0; for(int i = 1; i <= n; i++) { if(num[i] <= 1) continue; else if(sum[i] == 0) ans++; else if(sum[i] > 0) ans += sum[i] / 2; } printf("%d\n", ans); } return 0; }