原题：http://acm.fzu.edu.cn/problem.php?pid=2112
首先是，票上没有提到的点是不需要去的。
然后我们先考虑这个图有几个连通分量，我们可以用一个并查集来维护，假设有n个连通分量，我们就需要n-1条边把他们连起来。
最后对于每个联通分量来说，我们要使它能一次走完，就是要求他是否满足欧拉通路，也就是这个联通分量中至多有2个度为奇数的点，每多出2个度为奇数的点，就多需要一条边（因为单个连通分量的所有点的度数之和为偶数，所以不可能存在奇数个奇数度数的点）。
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define maxn 111111
using namespace std;
int f[maxn],du[maxn],odd[maxn],book[maxn];
int getf(int v){
if(f[v] == v){
return v;
}else{
f[v] = getf(f[v]);
return f[v];
}
}
void merge(int u,int v){
int a = getf(u);
int b = getf(v);
if(a!=b)
f[b] = a;
}
int main(){
int t;
scanf("%d",&t);
while(t--){
memset(du,,sizeof(du));//统计每个节点的度数
memset(odd,,sizeof(odd));//统计每个联通分量度数为奇数的节点个数
memset(book,,sizeof(book));//标记该点是否需要去
int n,m;
scanf("%d%d",&n,&m);
for(int i = ;i<=n;i++)//初始化
f[i] = i;
int u,v;
while(m--){
scanf("%d%d",&u,&v);
du[u]++;
du[v]++;
book[u] = ;
book[v] = ;
merge(u,v);
}
int cnt = ;//需要边的数量
for(int i = ;i<=n;i++){
if(book[i]){
if(f[i] == i)
cnt++;
if(du[i]&)//度数为奇数时，对其并查集根节点的值进行更新
odd[getf(i)]++;
}
}
for(int i = ;i<=n;i++){
if(f[i] == i)
cnt += max(,(odd[i]-)/);//统计每个联通分量的度数为奇数的节点所需要的边的个数
}
printf("%d\n",cnt-);
}
return ;
}