思路与算法

把每个0自由端视为独立的度1节点，用并查集统计有导线的分量。所有原焊点度大于2者必须熔一次，记总数B。单分量时答案B+奇点数/2。多分量时，每个分量贡献max(1,奇点数/2)次最终焊接；若它是全度2的纯环，还需额外熔一点开环。

正确性说明

最终圆环每个保留连接处度为2，故每个高分支原点至少要熔一次。按欧拉路线配对半边可一次完成该点全部分离，奇度分量留下最少o个自由端，形成o/2条路径。将所有路径焊成一个环恰需路径数次焊接。偶度分量若已有熔点可在同次熔操作中断开一对，免费形成一条路径；没有熔点的纯环必须另熔一点。只有一个闭分量时无须开环，得到两种公式。

复杂度

最多n+2m个含匿名自由端的节点。并查集合并、路径压缩及度统计近线性，保守O((n+m)log(n+m))时间，O(n+m)空间；初始化同阶。

易错点

两个写作0的端不是同一个焊点。自环贡献2度。无导线的原焊点忽略，度1点不熔。多纯环之间连接还要计最后闭合焊接，不能只算分量数减1。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<int> p(n + 2 * m + 1), d(p.size());
    iota(p.begin(), p.end(), 0);
    function<int(int)> f = [&](int x) {
        return p[x] == x ? x : p[x] = f(p[x]);
    };
    int N = n;
    for (int i = 0, u, v; i < m; i++) {
        cin >> u >> v;
        if (!u)
            u = ++N;
        if (!v)
            v = ++N;
        d[u]++;
        d[v]++;
        u = f(u);
        v = f(v);
        p[u] = v;
    }
    vector<int> odd(N + 1), branch(N + 1), active(N + 1);
    int comps = 0, burn = 0;
    for (int i = 1; i <= N; i++)
        if (d[i]) {
            int r = f(i);
            active[r] = 1;
            odd[r] += d[i] % 2;
            branch[r] += d[i] > 2;
            burn += d[i] > 2;
        }
    for (int x : active)
        comps += x;
    if (comps == 1) {
        int o = 0;
        for (int x : odd)
            o += x;
        cout << burn + o / 2 << '\n';
        return 0;
    }
    int ans = burn;
    for (int r = 1; r <= N; r++)
        if (active[r]) {
            ans += max(1, odd[r] / 2);
            if (!odd[r] && !branch[r])
                ans++;
        }
    cout << ans << '\n';
}