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