思路与算法

每组先确定家为首条街两端编号较小者，检查所有路口度数为偶。对街道编号建立邻接，按编号排序后用显式栈Hierholzer生成闭路；若未覆盖所有街或有奇点，输出题定失败语句。

正确性说明

输入保证街道互相连通，无向连通图具有欧拉回路当且仅当所有度数为偶。算法逐街使用唯一ID，并在退栈拼接各段，因此生成从家出发回家的全街回路。每街一次已经达到题目希望的最短游历条件；当前题面没有要求多解中只取某条。

复杂度

每组最多44点、1995街，邻接排序O(mlogm)，构造与初始化O(n+m)，空间O(n+m)。

易错点

自环在同一点加入两次邻接但边号只用一次。组结束是0 0，之后再一个0 0结束全部输入。失败文本大小写和标点保持原样；多解由街道连续性特判验收。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int x, y, z;
    while (cin >> x >> y && (x || y)) {
        vector<tuple<int, int, int>> e;
        int home = min(x, y);
        do {
            cin >> z;
            e.push_back({x, y, z});
            cin >> x >> y;
        } while (x || y);
        vector<vector<pair<int, int>>> g(45);
        int mx = 0;
        for (auto t : e) {
            int a = get<0>(t), b = get<1>(t), id = get<2>(t);
            g[a].push_back({b, id});
            g[b].push_back({a, id});
            mx = max(mx, id);
        }
        bool ok = true;
        for (auto &a : g) {
            if (a.size() % 2)
                ok = false;
            sort(a.begin(), a.end(), [](pair<int, int> a, pair<int, int> b) {
                return a.second < b.second;
            });
        }
        if (!ok) {
            cout << "Round trip does not exist.\n";
            continue;
        }
        vector<int> used(mx + 1), pos(45), st(1, home), edge, ans;
        while (!st.empty()) {
            int u = st.back();
            while (pos[u] < (int)g[u].size() && used[g[u][pos[u]].second])
                pos[u]++;
            if (pos[u] < (int)g[u].size()) {
                auto a = g[u][pos[u]++];
                used[a.second] = 1;
                st.push_back(a.first);
                edge.push_back(a.second);
            } else {
                st.pop_back();
                if (!edge.empty()) {
                    ans.push_back(edge.back());
                    edge.pop_back();
                }
            }
        }
        if (ans.size() != e.size()) {
            cout << "Round trip does not exist.\n";
            continue;
        }
        reverse(ans.begin(), ans.end());
        for (int i = 0; i < (int)ans.size(); i++)
            cout << ans[i] << (i + 1 == (int)ans.size() ? '\n' : ' ');
    }
}