题目地址：HDU 3018
求每个点的度数，，对于每个连通分支统计度数为奇数的个数，然后需要的次数就是个数/2。注意对于孤立的点不能算。
代码如下：
#include <iostream>#include <string.h>#include <math.h>#include <queue>#include <algorithm>#include <stdlib.h>#include <map>#include <set>#include <stdio.h>using namespace std;#define LL long long#define pi acos(-1.0)const int mod=1e9+7;const int INF=0x3f3f3f3f;const double eqs=1e-9;const int MAXN=100000+10;int head[MAXN], cnt, vis[MAXN], deg[MAXN], sum, ans;struct node{int i, v, next;}edge[4*MAXN];void add(int u, int v){edge[cnt].v=v;edge[cnt].next=head[u];head[u]=cnt++;}void dfs(int u){if(deg[u]&1) sum++;for(int i=head[u];i!=-1;i=edge[i].next){int v=edge[i].v;if(!vis[v]){vis[v]=1;dfs(v);}}}void init(){memset(head,-1,sizeof(head));cnt=0;memset(vis,0,sizeof(vis));memset(deg,0,sizeof(deg));ans=0;}int main(){int n, m, i, j, u, v;while(scanf("%d%d",&n,&m)!=EOF){init();while(m–){scanf("%d%d",&u,&v);if(u==v) continue ;add(u,v);add(v,u);deg[u]++;deg[v]++;}for(i=1;i<=n;i++){if(!vis[i]&&[i]){sum=0;dfs(i);if(sum) ans+=sum/2;else ans+=1;}}printf("%d\n",ans);}return 0;}
含泪播种的人一定能含笑收获。
