第一种思路：
首先计算图的连通分量个数c，没提到的点就不统计了。
然后对每个连通分量单独讨论，要使其有欧拉通路，则图中至多有2个度为奇数的点。
所以每多出2个度为奇数的点，我们就用一条线连起来（也就是多买一张票）。
（注意，因为单个连通分量的所有点的度数之和为偶数，所以不可能存在奇数个奇数度数的点）
最后答案=(c-1)+各个连通分量的max(0,(奇度数点个数-2)/2)
PS：不判连通分量也能过，这数据也太弱了吧。。
第二种思路：
使用并查集即可，不需要建图，比dfs快很多且省内存。
代码1：
/*796ms,4676KB*/ #include#include #include using namespace std; const int mx = 100005; vector v[mx]; int deg[mx];///点的度 int cnt; bool vis[mx]; void dfs(int i) { if (vis[i]) return; cnt += deg[i] & 1; vis[i] = true; for (int j = 0; j < v[i].size(); ++j) dfs(v[i][j]); } int main() { int T, n, m, a, b, i, allcnt; scanf(%d, &T); while (T--) { memset(deg, 0, sizeof(deg)); scanf(%d%d, &n, &m); for (i = 1; i <= n; ++i) v[i].clear(); while (m--) { scanf(%d%d, &a, &b); v[a].push_back(b); v[b].push_back(a); ++deg[a], ++deg[b]; } allcnt = -1; memset(vis, 0, sizeof(vis)); for (i = 1; i <= n; ++i) if (!vis[i] && deg[i]) { cnt = 0, dfs(i); ++allcnt; cnt = (cnt - 2) >> 1; if (cnt < 0) cnt = 0; allcnt += cnt; } printf(%d , allcnt); } return 0; }
代码2：
/*531ms,1576KB*/ #include#include #include using namespace std; const int mx = 100005; int fa[mx], rk[mx], cnt[mx]; bool odd[mx], has[mx]; int find(int x) {return ~fa[x] fa[x] = find(fa[x]) : x;} void merge(int x, int y) { x = find(x), y = find(y); if (x == y) return; ///已合并 if (rk[x] < rk[y]) fa[x] = y; else { fa[y] = x; if (rk[x] == rk[y]) ++rk[x]; } } int main() { //freopen(in.txt, r, stdin); int t, n, m, a, b, i, ans; scanf(%d, &t); while (t--) { memset(fa, -1, sizeof(fa)); memset(rk, 0, sizeof(rk)); memset(odd, 0, sizeof(odd)); memset(has, 0, sizeof(has)); scanf(%d%d, &n, &m); while (m--) { scanf(%d%d, &a, &b); odd[a] = !odd[a], odd[b] = !odd[b]; has[a] = has[b] = true; merge(a, b); } memset(cnt, 0, sizeof(cnt)); for (i = 1; i <= n; ++i) if (odd[i]) ++cnt[find(i)]; /// 统计每个连通分量的奇度数点个数 memset(odd, 0, sizeof(odd)); /// 改变意义:下面odd当vis使用 ans = -1; for (i = 1; i <= n; ++i) { a = find(i); if (has[a] && !odd[a]) { ans += max(1, cnt[a] >> 1); odd[a] = true; } } printf(%d , ans); } return 0; }