「John's trip」约翰的旅行

形式化题目

无向连通图， $m$ 条街道（编号 1…m）连接 $n$ 个路口。求从起点出发每条边恰好一次回到起点的回路，输出字典序最小的边编号序列；不存在输出 Round trip does not exist.。

正解

思路

1. 欧拉回路存在性

无向图存在欧拉回路 $\iff$ 每个顶点度数为偶数。

2. Hierholzer + 字典序贪心

标准 Hierholzer：从起点出发随意走，走不动时回溯记录边。要让输出字典序最小，只需每一步贪心选当前可用的编号最小的边：

每个顶点的邻接表按边编号升序排序；
迭代版用显式栈模拟递归，pos[u] 记录 $u$ 的邻接表扫描到哪了（跳过的边不再回看），摊还 $O(1)$ ；
回溯收集的边序逆序，整体翻转即回路正序。

3. 街道编号任意

输入的街道编号是任意整数（不一定 1…m），用集合判重。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-10 11:30
 * update_at: 2026-10-10 11:30
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const char* NO_ROUND_TRIP = "Round trip does not exist.";

// 路口邻接表：(街道编号, 另一端路口)，按街道编号升序
map<int, vector<pair<int, int> > > adj;
set<int> used_street;      // 已走过的街道编号
map<int, int> pos;         // 各路口扫描到邻接表的下标

// Hierholzer：从 start 出发走遍每条街道一次，返回字典序最小的街道序列
vector<int> euler_tour(int start) {
    vector<int> route;
    // 栈：(路口, 进入该路口所走的街道)，0 为哨兵
    vector<pair<int, int> > stack;
    stack.push_back(make_pair(start, 0));
    while (!stack.empty()) {
        int u = stack.back().first;
        int entered = stack.back().second;
        vector<pair<int, int> >& edges = adj[u];
        int i = pos[u];
        while (i < (int)edges.size() && used_street.count(edges[i].first)) i++;
        if (i < (int)edges.size()) {
            int street = edges[i].first;
            int v = edges[i].second;
            pos[u] = i + 1;
            used_street.insert(street);
            stack.push_back(make_pair(v, street));
        } else {
            pos[u] = i;
            stack.pop_back();
            if (entered) route.push_back(entered);
        }
    }
    reverse(route.begin(), route.end());
    return route;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    vector<string> out;
    while (true) {
        adj.clear();
        used_street.clear();
        pos.clear();
        // 读一组边的 (x, y, street)
        vector<tuple<int, int, int> > edges;
        int x, y, z;
        bool first = true;
        while (true) {
            if (!(cin >> x >> y)) {
                // 输入结束
                if (edges.empty() && first) {
                    // 直接结束
                    goto done;
                }
                break;
            }
            first = false;
            if (x == 0 && y == 0) break;
            cin >> z;
            edges.push_back(make_tuple(x, y, z));
        }
        if (edges.empty()) break;

        int start = min(get<0>(edges[0]), get<1>(edges[0]));
        for (size_t i = 0; i < edges.size(); i++) {
            int a = get<0>(edges[i]), b = get<1>(edges[i]), s = get<2>(edges[i]);
            adj[a].push_back(make_pair(s, b));
            adj[b].push_back(make_pair(s, a));
        }
        for (map<int, vector<pair<int, int> > >::iterator it = adj.begin(); it != adj.end(); ++it)
            sort(it->second.begin(), it->second.end());

        // 连通性（从 start 出发）
        set<int> seen;
        vector<int> frontier;
        seen.insert(start);
        frontier.push_back(start);
        while (!frontier.empty()) {
            int u = frontier.back(); frontier.pop_back();
            for (size_t i = 0; i < adj[u].size(); i++) {
                int v = adj[u][i].second;
                if (!seen.count(v)) {
                    seen.insert(v);
                    frontier.push_back(v);
                }
            }
        }
        bool all_even = true;
        for (map<int, vector<pair<int, int> > >::iterator it = adj.begin(); it != adj.end(); ++it) {
            if (it->second.size() % 2 != 0) { all_even = false; break; }
        }
        bool connected = (seen.size() == adj.size());

        if (all_even && connected) {
            vector<int> route = euler_tour(start);
            string s;
            for (size_t i = 0; i < route.size(); i++) {
                if (i) s += " ";
                s += to_string(route[i]);
            }
            out.push_back(s);
        } else {
            out.push_back(NO_ROUND_TRIP);
        }
    }
done:
    for (size_t i = 0; i < out.size(); i++) cout << out[i] << "\n";
    return 0;
}

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-02 03:07
# update_at: 2026-10-02 03:07

import sys

NO_ROUND_TRIP = 'Round trip does not exist.'


def euler_tour(start: int, adj: dict[int, list[tuple[int, int]]]) -> list[int]:
    """从 start 出发走遍每条街道且只走一次再回到 start，返回街道编号序列。

    邻接表按街道编号升序：每一步都贪心走"当前能用、编号最小的街道"，走不动时再回溯，
    得到的回路字典序最小。栈里存 (路口, 进入该路口所走的街道)，回溯时收集到的编号是
    逆序的，最后整体翻转一次。
    """
    used: set[int] = set()      # 街道编号是任意整数（不一定 1..n），用集合判断是否走过
    pos: dict[int, int] = {}    # 各路口扫描到邻接表的下标，跳过已用街道的代价才能摊还成 O(1)
    route: list[int] = []
    stack = [(start, 0)]        # 哨兵 0：出发点没有"进入街道"
    while stack:
        u, entered = stack[-1]
        edges = adj[u]
        i = pos.get(u, 0)
        while i < len(edges) and edges[i][0] in used:   # edges[i] = (街道编号, 另一端路口)
            i += 1              # 同一路口可能被多次经过，被跳过的街道下标只前进不后退
        if i < len(edges):
            street, v = edges[i]
            pos[u] = i + 1      # 这条街道已经被这一步占用，下次直接从下一条看起
            used.add(street)
            stack.append((v, street))
        else:
            pos[u] = i
            stack.pop()
            if entered:
                route.append(entered)
    route.reverse()
    return route


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    out: list[str] = []

    while True:
        edges: list[tuple[int, int, int]] = []
        while True:
            x, y = next(data), next(data)
            if x == 0 and y == 0:
                break
            edges.append((x, y, next(data)))
        if not edges:
            break               # 空用例的 0 0：整份输入结束

        start = min(edges[0][0], edges[0][1])   # 题面：第一条街道两端较小编号的路口是家

        adj: dict[int, list[tuple[int, int]]] = {}
        for x, y, street in edges:
            adj.setdefault(x, []).append((street, y))
            adj.setdefault(y, []).append((street, x))
        for neighbours in adj.values():
            neighbours.sort()   # 按街道编号升序，Hierholzer 才取得到字典序最小的回路

        seen = {start}
        frontier = [start]
        while frontier:
            for _, v in adj[frontier.pop()]:
                if v not in seen:
                    seen.add(v)
                    frontier.append(v)

        all_degrees_even = all(len(neighbours) % 2 == 0 for neighbours in adj.values())
        connected = len(seen) == len(adj)   # 所有路口都在出发点的连通块里

        out.append(
            ' '.join(map(str, euler_tour(start, adj)))
            if all_degrees_even and connected
            else NO_ROUND_TRIP
        )

    print('\n'.join(out))


if __name__ == "__main__":
    solve()

复杂度

时间复杂度： $O(m\log m)$ （排序）+ $O(m)$ （Hierholzer）。
空间复杂度： $O(m)$ 。

总结

「字典序最小欧拉回路」= Hierholzer + 每步贪心选最小编号边 + 邻接表预排序。
迭代版 Hierholzer 用显式栈 + pos 下标前进，避免递归爆栈并把跳过代价摊还掉。
度数奇偶是欧拉回路存在性的唯一判据（连通图）。

「John's trip」 约翰的旅行

目录

形式化题目

正解

思路

1. 欧拉回路存在性

2. Hierholzer + 字典序贪心

3. 街道编号任意

代码

复杂度

总结

「John's trip」约翰的旅行