思路与算法

先用并查集合并无向边的两端，并统计每个点的度数。对每个有边的连通分量，设奇度顶点有 o 个：o=0 时需要1笔，否则需要 o/2 笔。把所有有边分量的答案相加；孤立点不计笔数，完全没有边时答案为0。

正确性说明

一笔最多提供两个端点，所以一个分量中的 o 个奇度顶点至少需要 o/2 笔；非空且没有奇度点的分量也至少要1笔。把奇度点两两配对并加上临时边，可得到欧拉回路；再删掉临时边，回路被切成恰好 o/2 条道路。没有奇度点时，原图的一条欧拉回路即可。因此各分量的下界都能达到，且不同分量的边无法一笔相连，答案可以相加。

复杂度

每组时间 O((N+M)α(N))，额外空间 O(N)。程序不需要保存全部边。

易错点

不能只统计整张图的奇度点，还要区分连通分量。没有边的点不需要单独一笔。输入持续到文件结束，空行会被正常跳过。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    while (cin >> n >> m) {
        vector<int> p(n), sz(n, 1), degree(n), odd(n), active(n);
        iota(p.begin(), p.end(), 0);
        function<int(int)> find = [&](int u) {
            return p[u] == u ? u : p[u] = find(p[u]);
        };
        for (int i = 0; i < m; i++) {
            int a, b;
            cin >> a >> b;
            --a;
            --b;
            degree[a]++;
            degree[b]++;
            a = find(a);
            b = find(b);
            if (a != b) {
                if (sz[a] < sz[b])
                    swap(a, b);
                p[b] = a;
                sz[a] += sz[b];
            }
        }
        for (int v = 0; v < n; v++)
            if (degree[v]) {
                int c = find(v);
                active[c] = 1;
                odd[c] += degree[v] & 1;
            }
        long long ans = 0;
        for (int i = 0; i < n; i++)
            if (active[i])
                ans += max(1, odd[i] / 2);
        cout << ans << '\n';
    }
}