本文主要是介绍fzu 2112 Tickets(欧拉道路），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：fzu 2112 Tickets
题目大意：给出n和m，表示有n个城市和m张票，现在要进行一场旅行，要求将所有的票使用掉，问还需要自己买几张票。
解题思路：欧拉道路的题目，只要输入中出现的城市才需要去考虑它的度数，并且要考虑说两个图是否联通。
我的做法是，读入数据的时候，标记出现过的点，并且记录每个点的度数，并查集记录点属于哪一个集合。
然后首先保证每个子的联通图为欧拉通路（度数为奇数的点不超过2），然后在加上集合个数 - 1.
#include <stdio.h>
#include <string.h>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;
}
这篇关于fzu 2112 Tickets(欧拉道路）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
