题目链接：fzu 2112 Tickets
题目大意：给出n和m，表示有n个城市和m张票，现在要进行一场旅行，要求将所有的票使用掉，问还需要自己买几张票，
fzu 2112 Tickets(欧拉道路）
。解题思路：欧拉道路的题目，只要输入中出现的城市才需要去考虑它的度数，并且要考虑说两个图是否联通。
我的做法是，读入数据的时候，标记出现过的点，并且记录每个点的度数，并查集记录点属于哪一个集合。
然后首先保证每个子的联通图为欧拉通路（度数为奇数的点不超过2），然后在加上集合个数 - 1.
#include
#include
const int N = 100005;
int n, m, f[N], d[N], vis[N];
int cnt, rec[N], g[N];
int getfar(int x) {
int p, q, t;
p = q = x;
while (p != f[p]) p = f[p];
while (q != f[q]) {
t = q;
q = f[q];
f[q] = p;
}
return p;
}
void init() {
memset(d, 0, sizeof(d));
memset(g, 0, sizeof(g));
memset(vis, 0, sizeof(vis));
for (int i = 1; i <= n; i++) f[i] = i;
scanf("%d%d", &n, &m);
int a, b;
for (int i = 0; i < m; i++) {
scanf("%d%d", &a, &b);
vis[a] = vis[b] = 1;
d[a]++, d[b]++;
int x = getfar(a), y = getfar(b);
if (x != y) f[y] = x;
}
}
void handle() {
cnt = 0;
for (int i = 1; i <= n; i++) {
if (vis[i]) {
int x = getfar(i);
if (vis[x] != 2) rec[cnt++] = x;
if (d[i] & 1) g[x]++;
vis[x] = 2;
}
}
}
int solve() {
int ans = cnt - 1;
for (int i = 0; i < cnt; i++)
if (g[rec[i]] > 2) ans = ans + g[rec[i]] / 2 - 1;
return ans;
}
int main () {
int cas;
scanf("%d", &cas);
while (cas--) {
init();
handle();
printf("%d\n", solve());
}
return 0;
}