Amazon NG VO 每轮先 BQ 再编程，这道"飞机航线遍历所有城市"是其中一轮的编程题。很多人一看到"图 + 遍历"就误判成拓扑排序——其实它是欧拉路径。这篇按 oavoservice 学员的复盘讲清判定与解法，以及一个很妙的 follow-up：当每个机场只能飞往一个城市时，图退化成链表，题目随之降维。文末附 VO辅助 / VO代面 的对接路径，给正在校招、转码、SDE 求职的同学一个实战参考。
一、题目背景
| 维度 | 详情 |
|---|---|
| 轮次 | Amazon NG VO 编程轮（先 BQ 后编程） |
| 题型 | 图论 / 欧拉路径 |
| 语言 | 自选，Python 常见 |
| 考察 | 题型识别、图遍历、连通性、follow-up 降维 |
二、题目
给定一组飞机航线图（城市为节点，航线为边），问能否找到一条路线，让飞行员遍历所有航线（每条边走且仅走一次），把所有城市连起来。
三、拆题：这是欧拉路径，不是拓扑排序
很多 CCD（candidate）一看到"图 + 遍历"就误判成拓扑排序——其实不是。这题要求"每条边恰好走一次"，正是欧拉路径（Eulerian Path）。
判定条件（无向图）：图连通，且度数为奇数的顶点恰好为 0 个（欧拉回路，可从任意点出发回到原点）或 2 个（欧拉路径，从一个奇度点走到另一个）。
def has_eulerian_path(n, edges):
# 无向图：统计度数 + 连通性
from collections import defaultdict
deg = defaultdict(int)
adj = defaultdict(list)
for u, v in edges:
deg[u] += 1
deg[v] += 1
adj[u].append(v)
adj[v].append(u)
odd = sum(1 for node in deg if deg[node] % 2 == 1)
if odd not in (0, 2):
return False
# 连通性：从任一有边的点 DFS，确认所有有边的点都可达
start = next(iter(deg))
seen = set()
stack = [start]
while stack:
u = stack.pop()
if u in seen:
continue
seen.add(u)
for v in adj[u]:
if v not in seen:
stack.append(v)
return len(seen) == len(deg)
时间复杂度：O(V + E)。空间复杂度：O(V + E)。
四、Follow-up：每个机场只能飞往一个城市 → 退化成链表重建
追问：如果每个城市的机场只能到达一个城市（每个节点出度为 1），怎么优化？
这一限制让 input 从图退化成了链表：每个节点只有一个后继，整条航线就是一条单链。问题随之从欧拉路径变成了重建链表 / 找链表顺序——给定一堆 (from, to) 对，拼出从起点到终点的唯一顺序。
def reconstruct_route(pairs):
# pairs: [(from, to)], 每个 from 唯一 → 实为单链表
nxt = {a: b for a, b in pairs}
targets = set(nxt.values())
# 起点：从未作为任何边的终点出现
start = next(a for a in nxt if a not in targets)
route = [start]
while route[-1] in nxt:
route.append(nxt[route[-1]])
return route
时间复杂度：O(n)。空间复杂度：O(n)。
刷题关注本质：图退化成链表后，万变不离其宗——结构变简单，解法也随之降维。认出这层退化，就能从复杂的欧拉路径快速切到 O(n) 的链表重建。
五、临场提醒
- "遍历所有边各一次"是欧拉路径的信号，别条件反射写成拓扑排序。
- 欧拉路径要同时查度数奇偶和连通性，两个条件缺一不可。
- follow-up 常通过加约束降维（图→链表），认出退化结构就能快速给更优解。
- 先口头讲清"这是欧拉路径而非拓扑排序"，纠正误区本身就是加分点。
FAQ
Q1：飞机航线题为什么是欧拉路径不是拓扑排序？
因为要求"每条边恰好走一次"，这正是欧拉路径的定义；拓扑排序解决的是有向无环图的节点先后顺序，二者不是一回事。无向图欧拉路径的判定是连通且奇度顶点数为 0 或 2。
Q2：欧拉路径和欧拉回路有什么区别？
欧拉回路要求起点终点相同，无向图里所有顶点度数为偶；欧拉路径起终点不同，恰好有 2 个奇度顶点（起点和终点）。两者都要求图连通（忽略孤立点）。
Q3：follow-up 里图为什么会退化成链表？
当每个节点出度限制为 1，每个城市只能飞往唯一一个城市，整个结构就成了"每个节点恰好一个后继"的单链——本质是链表。于是只需用哈希表建立 from→to，从起点顺着走即可，O(n) 重建。
Q4：Amazon NG 编程轮怎么高效准备？
按图论（欧拉路径 / 拓扑 / 连通）、树、链表、DP 分专题刷，每类限时练并口头讲思路，同时备好 BQ。需要按 Amazon NG 题型 + BQ 做限时 mock、逐题讲解或 VO辅助 / VO代面 全程对接，可以走下面的路径定制。
正在准备 Amazon NG VO？
Amazon NG 是 BQ + 编程的 loop，编程爱在经典图论题上设 follow-up 降维。oavoservice 提供 Amazon 全流程陪练：欧拉路径 / 图论 / 链表 / DP 高频题限时模拟，题型识别与 follow-up 应变逐题打磨，16 条 LP 的 STAR 故事同步准备。教练含大厂资深工程师与 Bar Raiser 视角，支持 VO辅助 / VO代面 全程对接。
立即添加微信 Coding0201，获取 Amazon 真题与陪练。
联系方式
- 微信：Coding0201
- Email：[email protected]
- Telegram：@OAVOProxy