「一本通 3.7 练习 3」John's Trip

形式化题目

给定无向图 $G=(V,E)$ ，每条边（街）带唯一编号 $1,\dots,m$ ，允许重边与自环，且所有街互相连通。起点 $s$ 取输入中第一条街两端编号较小的路口。对每组数据判断是否存在一条从 $s$ 出发、经过每条边恰好一次、最终回到 $s$ 的闭迹（欧拉回路）；存在则输出该闭迹依次经过的街编号序列（任意一条合法回路均可），否则输出 Round trip does not exist.。

正解

思路

朴素做法：搜索枚举。 从起点出发，每一步枚举还没走过的街，回溯寻找一条走遍所有街并回到起点的行走。街最多 $1995$ 条，分支数随路口度数增长，搜索树是指数级的，不可行。但它给出第一条线索：闭迹每经过一个路口都是一进一出，"每条边恰好一次"这个要求会强烈约束各路口的度数奇偶。

判定：度数全偶。 闭迹经过任意顶点消耗 $2$ 度，起点与终点又是同一个点，所以所有顶点度数必须为偶数；在题面保证"所有街连通"的前提下，全偶也是充分的（这就是无向图欧拉回路判定定理）。因此只要存在奇数度路口，回路必不存在。

构造：Hierholzer 贪心延伸 + 拼接。 从起点出发，每个路口按街编号升序取第一条没走过的街，一直走到走不动为止。三个关键观察把算法拼完整：

贪心必停回出发点：若图中所有顶点都是偶数度，贪心极大路径不可能停在别的路口——反证：设停在 $u \neq s$ ，删掉走过的边后，中间顶点进出成对仍为偶， $u$ 被掏空剩 $0$ 度，而 $s$ 被用掉的边数为奇（首次出发 $1$ 条，此后每次进出各一条成对出现），剩余度数为奇，剩余子图里只剩一个奇度顶点，与握手定理（奇度顶点必成对出现）矛盾。
失败信号免费获得：于是"某次贪心停在它自己的出发点以外"就等价于"存在奇数度路口"，不需要单独预判度数——贪心过程自己会暴露回路不存在（样例第二组：路口 $2$ 度数为 $3$ 、路口 $4$ 度数为 $1$ ；第一条闭合路径能回到起点，但推进到路口 $2$ 重新贪心时，走完街 $4$ 停在了路口 $4$ ）。
剩余边靠拼接收尾：第一条闭合路径可能只覆盖一部分边。沿已有回路逐个路口推进，每个路口重新贪心走出的仍是闭合路径，把它插到当前位置前面，回路变长且仍是合法闭迹；整圈推进结束时所有街都已入回路（有街连通性保证剩余部分一定挂在回路上，推进到交点路口就会被抽干）。

样例回路

下表按回路顺序逐步展开样例第一组：起点是输入第一行（街 $1$ 连接路口 $1$ 与 $2$ ）中编号较小的路口 $1$ ，输出 1 2 3 5 4 6 表示依次走过这六条街。

步骤	街编号	从路口	到路口
1	1	1	2
2	2	2	3
3	3	3	2
4	5	2	1
5	4	1	3
6	6	3	1
—	回到起点	1	—

观察每一步的取边：路口 $2$ 上连着街 1、2、3、5，街 1 已走，于是取编号最小的可用街 2；路口 3 上街 2 已走，取街 3。编号升序的取边顺序让输出确定，且第 6 步恰好回到起点 1，每条街用且仅用一次——这就是合法回路的验证方式。

闭合路径的拼接

当第一条闭合路径没走完所有边时，Hierholzer 把新走出的闭合路径插到推进游标前面：

text

1
2
3已有回路:  ... --- [prev] ---v--- [cursor] --- ...
闭合路径:        v === e1 === ... === ek === v
拼接之后:  ... --- [prev] --- e1 === ... === ek --- [cursor] --- ...

游标停在路口 $v$ 时重新贪心，走出的路径首尾都在 $v$ ；把它接到 [prev] 与 [cursor] 之间，只需要改这四条链表指针，回路边数增加且仍首尾相接。随后游标沿回路后退一条街继续推进，退回到首街时整圈扫描完成，沿 nxt 链走一圈输出即为答案。自环的两端是同一路口，走完后停在原地继续贪心，且自环给顶点贡献 $2$ 度、不影响判定。

代码

extend_trail 对应贪心延伸，euler_circuit 对应判定、拼接与输出，solve 负责按 0 分组读入与拼接输出行。

Python 版：

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
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
123
124
125
126
127
128
129
130
131#!/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-09-30 16:39
# update_at: 2026-09-30 16:39

import sys

UNUSED = -1   # nxt[i] 的取值：这条街还没走过
PENDING = -2  # nxt[i] 的取值：街已进路径但还没并进回路，同样按"走过"处理


def extend_trail(
    junction: int,
    streets: list[tuple[int, int, int]],
    adj: list[list[int]],
    nxt: list[int],
    prv: list[int],
    ptr: list[int],
) -> tuple[int, int, int]:
    """从 junction 沿没走过的街贪心走到走不动，返回 (首街, 尾街, 停住的路口)。"""
    first, last = -1, -1
    while True:
        # 每个路口的关联街按编号升序存放，ptr 记住查到哪了，跳过已走的街
        incident, p = adj[junction], ptr[junction]
        while p < len(incident) and nxt[incident[p]] != UNUSED:
            p += 1
        ptr[junction] = p
        if p == len(incident):
            return first, last, junction  # 这个路口再没有没走的街
        s = incident[p]
        if first == -1:  # 新路径的第一条街
            first = s
            prv[s] = PENDING
        else:
            prv[s] = last
            nxt[last] = s
        nxt[s] = PENDING
        last = s
        x, y, _ = streets[s]
        junction = x if x != junction else y  # 走到街的另一端；自环两端相同则原地不动


def euler_circuit(streets: list[tuple[int, int, int]], home: int) -> list[int] | None:
    """Hierholzer 求经过每条街恰好一次、从 home 出发又回到 home 的街编号序列。

    streets 按街编号升序排列，于是每个路口的取边顺序也是编号升序；
    回路不存在（存在奇数度路口导致贪心路停在别处）时返回 None。
    """
    n = len(streets)
    size = max(max(x, y) for x, y, _ in streets) + 1
    adj: list[list[int]] = [[] for _ in range(size)]
    for i, (x, y, _) in enumerate(streets):
        adj[x].append(i)
        if y != x:
            adj[y].append(i)

    nxt = [UNUSED] * n  # 回路中的下一条街
    prv = [UNUSED] * n  # 回路中的上一条街
    ptr = [0] * size    # 各路口关联街的扫描位置

    first, last, stop = extend_trail(home, streets, adj, nxt, prv, ptr)
    if stop != home:  # 贪心路停在别的路口：该路口奇数度，回路不存在
        return None
    prv[first] = last
    nxt[last] = first  # 首尾相接成一个闭合回路
    cursor, junction = first, home

    while True:
        # 当前路口再贪心走出的必是闭合路径：插到 cursor 街前面，直到走不动为止
        while True:
            s, e, stop = extend_trail(junction, streets, adj, nxt, prv, ptr)
            if stop != junction:
                return None  # 停在别处：奇数度路口，回路不存在
            if s == -1 or e == -1:
                break
            before = prv[cursor]
            prv[s] = before
            nxt[before] = s
            prv[cursor] = e
            nxt[e] = cursor
        cursor = prv[cursor]  # 沿回路后退一条街，继续在下一个路口找可并入的路径
        x, y, _ = streets[cursor]
        junction = x if x != junction else y  # 路口挪到这条街的另一端
        if cursor == first:  # 退回起点：整圈扫完，所有街都已进回路
            break

    circuit: list[int] = []
    s = first
    while True:
        circuit.append(streets[s][2])
        s = nxt[s]
        if s == first:
            break
    return circuit


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

    while pos + 1 < len(tokens):
        # 一组数据：若干 "x y z"（街 z 连接路口 x、y），"0 0" 结束本组，单独的 0 结束输入
        group: list[tuple[int, int, int]] = []
        while pos + 1 < len(tokens):
            x, y = tokens[pos], tokens[pos + 1]
            pos += 2
            if x == 0 or y == 0:
                break
            z = tokens[pos]
            pos += 1
            group.append((x, y, z))
        if not group:
            break  # 又读到 0：整个输入结束

        home = min(group[0][0], group[0][1])  # 起点：第一条街两端编号较小的路口
        streets = sorted(group, key=lambda street: street[2])  # 街编号升序决定取边顺序
        circuit = euler_circuit(streets, home)
        out.append(
            'Round trip does not exist.'
            if circuit is None
            else ' '.join(map(str, circuit))
        )

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


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151/**
 * 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-05 06:32
 * update_at: 2026-10-05 06:51
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXM = 2005; // 街最多 1995 条
const int MAXV = 60;   // 路口最多 44 个

typedef long long ll;

struct Street {
    int x, y, id; // 街连接的两个路口与街编号
};

int m;                 // 本组街数
int home_v;            // 起点：本组第一条街两端编号较小的路口
Street st[MAXM];       // 每条街的信息
vector<int> adj[MAXV]; // adj[v]：与路口 v 相连的街下标，按街编号升序
int adjlen[MAXV];      // adj[v] 的长度，避免反复取 size
int nxt_e[MAXM];       // 回路中当前街的下一条街：-1 未走过，-2 已走但还没并进回路
int prv_e[MAXM];       // 回路中当前街的上一条街
int ptr[MAXV];         // 各路口在 adj 里扫描到的位置，只增不减
int trail_head, trail_tail, stop_v; // extend_trail 的结果：首街、尾街、停住的路口
int anchor;                        // 回路首街（锚点），作退回起点的判定

// 按街编号升序排序，保证每个路口取边时也是编号升序。
bool cmp_street(const Street &a, const Street &b) {
    return a.id < b.id;
}

// 从 junction 沿没走过的街贪心延伸到走不动为止，结果存入 trail_head / trail_tail / stop_v。
void extend_trail(int junction) {
    trail_head = -1;
    trail_tail = -1;
    while (true) {
        int p = ptr[junction];
        // 跳过这条街上已经走过的街
        while (p < adjlen[junction] && nxt_e[adj[junction][p]] != -1) p++;
        ptr[junction] = p;
        if (p == adjlen[junction]) { // 这个路口再没有没走过的街，贪心停止
            stop_v = junction;
            return;
        }
        int s = adj[junction][p];
        if (trail_head == -1) { // 新路径的第一条街
            trail_head = s;
            prv_e[s] = -2;
        } else {
            prv_e[s] = trail_tail;
            nxt_e[trail_tail] = s;
        }
        nxt_e[s] = -2;
        trail_tail = s;
        // 走到街的另一端；自环两端相同，原地不动
        junction = (st[s].x == junction) ? st[s].y : st[s].x;
    }
}

// Hierholzer：构造从起点出发、经过每条街恰好一次又回到起点的回路。
// 贪心路径停在出发点以外说明存在奇数度路口，回路不存在，返回 false。
bool euler_circuit() {
    for (int v = 0; v < MAXV; v++) ptr[v] = 0;
    for (int i = 1; i <= m; i++) {
        nxt_e[i] = -1;
        prv_e[i] = -1;
    }

    extend_trail(home_v);
    if (stop_v != home_v) return false; // 停在别的路口：奇数度，回路不存在
    anchor = trail_head;               // 第一条闭合路径的首街就是回路锚点
    prv_e[anchor] = trail_tail;
    nxt_e[trail_tail] = anchor; // 首尾相接成闭合回路
    int cursor = anchor;
    int junction = home_v;
    while (true) {
        // 在当前路口反复贪心，把新走出的闭合路径插到 cursor 街前面
        while (true) {
            extend_trail(junction);
            if (stop_v != junction) return false; // 奇数度路口，回路不存在
            if (trail_head == -1) break;          // 当前路口的街已全部入回路
            int before = prv_e[cursor];
            prv_e[trail_head] = before;
            nxt_e[before] = trail_head;
            prv_e[cursor] = trail_tail;
            nxt_e[trail_tail] = cursor;
        }
        // 沿回路后退一条街：先退 cursor，再以新 cursor 街的另一端作为新路口，
        // 这样新路口正好对上 cursor 与前一条街之间的接入位置
        cursor = prv_e[cursor];
        junction = (st[cursor].x == junction) ? st[cursor].y : st[cursor].x;
        if (cursor == anchor) break; // 退回锚点街：整圈扫完，所有街都已入回路
    }
    return true;
}

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

    while (true) {
        int x, y;
        m = 0;
        // 一组数据：若干 "x y z"，遇到带 0 的一行结束本组
        while (cin >> x >> y) {
            if (x == 0 || y == 0) break;
            int z;
            cin >> z;
            m++;
            st[m].x = x;
            st[m].y = y;
            st[m].id = z;
        }
        if (!cin || m == 0) break; // 又读到 0：整个输入结束

        home_v = min(st[1].x, st[1].y); // 起点要在排序前从输入第一条街取
        sort(st + 1, st + m + 1, cmp_street);
        for (int v = 0; v < MAXV; v++) {
            adj[v].clear();
            adjlen[v] = 0;
        }
        // 街已按编号升序，顺序挂进邻接表后每个路口的取边顺序自然也是升序
        for (int i = 1; i <= m; i++) {
            adj[st[i].x].push_back(i);
            adjlen[st[i].x]++;
            if (st[i].y != st[i].x) { // 自环只挂一次
                adj[st[i].y].push_back(i);
                adjlen[st[i].y]++;
            }
        }

        if (euler_circuit()) {
            // 从锚点街沿 nxt_e 走一圈，依次输出街编号
            int s = anchor;
            while (true) {
                cout << st[s].id;
                s = nxt_e[s];
                if (s == anchor) break;
                cout << ' ';
            }
            cout << '\n';
        } else {
            cout << "Round trip does not exist.\n";
        }
    }
    return 0;
}

复杂度

时间复杂度：每组 $\mathcal{O}(|E|\log|E|)$ ，由街按编号排序主导；主体部分（建表、贪心延伸、拼接、输出）为 $\mathcal{O}(|V|+|E|)$ ——ptr 只增不减，每条街恰好被取一次，每次拼接只改 $4$ 个指针。 $|E|\leqslant 1995$ ，实际毫秒级完成。
空间复杂度： $\mathcal{O}(|V|+|E|)$ ，邻接表与 nxt / prv / ptr 三个线性数组。

总结

"每条街走一次并回到起点"就是欧拉回路：判定看度数是否全偶，构造用 Hierholzer——贪心延伸出闭合路径，逐路口把新闭合路径拼进已有回路，整圈推进即得答案。本题两个容易踩的细节：失败不必预先统计度数，贪心停在出发点以外就是不存在的信号；起点取输入第一条街两端的较小路口，必须在按街编号排序之前记下。