思路与算法

先统计各点度数，自环对度数贡献2。若奇度点数不是0或2则无解。有2个奇点时从奇点出发，否则从任意非零度点出发。用带边编号的邻接表与栈执行Hierholzer：当前点还有未用边就走该边并标记；没有未用边就弹栈、加入后序答案，最后逆序。若答案长度不是m+1，说明存在未遍历的有边分量，输出No solution。

正确性说明

无向图欧拉道路要求所有非零度点连通，且奇点数为0或2；有奇点时它们必须是端点。Hierholzer在局部走完后回填闭合段，每条边以独立编号只使用一次。非零度连通且奇度条件满足时，这些段能拼接为一条完整道路。反之，最终长度少于m+1意味着有边未从起始分量到达，不存在覆盖所有边的一条道路。

复杂度

读入与度数初始化O(n+m)。本实现排序邻接表以稳定输出，排序总计O(m log m)；Hierholzer的当前弧扫描O(n+m)。空间O(n+m)，栈最多m+1个顶点。

易错点

自环须计两次度数但仅使用一次边，重边必须分配不同边号。不能用邻接矩阵布尔量合并重边。孤立点不影响已有边的一笔画。输出由特判逐条扣边验证，任意合法欧拉道路均可。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<pair<int, int>>> a(n + 1);
    vector<int> degree(n + 1);
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        a[u].push_back({v, i});
        a[v].push_back({u, i});
        ++degree[u];
        ++degree[v];
    }
    int start = 0, odd = 0;
    for (int i = 1; i <= n; ++i) {
        sort(a[i].begin(), a[i].end());
        if (degree[i] && !start)
            start = i;
        if (degree[i] % 2)
            ++odd;
    }
    if (odd != 0 && odd != 2) {
        cout << "No solution\n";
        return 0;
    }
    if (odd == 2)
        for (int i = 1; i <= n; ++i)
            if (degree[i] % 2) {
                start = i;
                break;
            }
    vector<int> st(1, start), ans, at(n + 1);
    vector<bool> used(m);
    while (st.size()) {
        int u = st.back();
        while (at[u] < (int)a[u].size() && used[a[u][at[u]].second])
            ++at[u];
        if (at[u] == (int)a[u].size()) {
            ans.push_back(u);
            st.pop_back();
        } else {
            auto e = a[u][at[u]++];
            used[e.second] = true;
            st.push_back(e.first);
        }
    }
    if ((int)ans.size() != m + 1) {
        cout << "No solution\n";
        return 0;
    }
    reverse(ans.begin(), ans.end());
    for (int i = 0; i < (int)ans.size(); ++i)
        cout << (i ? " " : "") << ans[i];
    cout << "\n";
}