思路与算法

逐个数据集统计无向度数，并用并查集合并边端点。有欧拉回路当且仅当所有顶点度数为偶数，且所有非零度顶点在同一连通块。满足输出1，否则0；单独0结束输入。

正确性说明

封闭地遍历每条边一次时，每次进点必配一次出点，所以每个顶点度数偶；所有实际边也必须处在同一连通块。反之非零度部分连通且度数均偶时，从有边顶点不断走未用边必回起点，若还有未用边可从已有回路上的连接点继续构造小回路并拼接，最终覆盖全部边。孤立点没有要走的边，不影响判定。

复杂度

每组O(N+M alpha(N))时间、O(N)空间，含度数与并查集初始化；输入边流式处理，不存整图。

易错点

两个分离的环虽然度数全偶也不能输出1。重边分别计数，自环给度数加2。此题只判断存在，不输出路径；结束标志只有一个0，不必再读M。

参考代码（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 && n) {
        cin >> m;
        vector<int> p(n), deg(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 u, v;
            cin >> u >> v;
            --u;
            --v;
            deg[u]++;
            deg[v]++;
            p[find(u)] = find(v);
        }
        bool ok = true;
        int root = -1;
        for (int i = 0; i < n; i++)
            if (deg[i]) {
                if (deg[i] % 2)
                    ok = false;
                if (root < 0)
                    root = find(i);
                else if (find(i) != root)
                    ok = false;
            }
        cout << (ok ? 1 : 0) << "\n";
    }
}