题目重点：用有向欧拉路径、Hierholzer 算法和边数核验处理重复票与无解情况。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 每张票是有向边，含相同起终点的票仍是不同实体；路线必须恰好用每张票一次。
- 若有多条合法路线，返回任意一条；题目未明确字典序规则。无解返回 None；空票列表返回空路线。
- 不提供固定起点，若面试官指定起点，还必须验证它与欧拉路径的起点一致。
解题路线
- 统计每个机场的出度和入度。有向欧拉路径的必要条件是恰有一个 out−in=1 的起点、一个 in−out=1 的终点，其余差为 0；或者所有点差为 0 构成回路。
- 度数只给局部条件：A→B→A 与 C→D→C 两个断开回路都平衡，仍无法从一个机场用完所有票。
- 从候选起点用 Hierholzer 算法：沿未用边推进，走不动时把顶点压入逆序答案，最后反转。
- 最终路线必须有 E+1 个顶点，说明 E 张票全被消耗；本文还用 66,430 张至多五边的有向重边图对独立回溯搜索核对存在性与边多重集。
手动走一遍
票 [A→B, B→A, C→D, D→C] 全部入出度平衡，随便取 A 只能得到 A,B,A，长度为 3 而不是 5，须返回无解。票 [A→B, A→C, B→A] 可返回 A,B,A,C，重复经过 A 但每张票只用一次。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
from collections import defaultdict
def itinerary_using_all(tickets: list[tuple[str, str]]) -> list[str] | None:
"""Return any directed Euler trail using every ticket once, or None."""
if not tickets:
return []
adjacency: dict[str, list[str]] = defaultdict(list)
indegree: dict[str, int] = defaultdict(int)
outdegree: dict[str, int] = defaultdict(int)
for origin, destination in tickets:
adjacency[origin].append(destination)
outdegree[origin] += 1
indegree[destination] += 1
starts, ends = [], []
for vertex in indegree.keys() | outdegree.keys():
difference = outdegree[vertex] - indegree[vertex]
if difference == 1:
starts.append(vertex)
elif difference == -1:
ends.append(vertex)
elif difference != 0:
return None
if len(starts) == len(ends) == 1:
start = starts[0]
elif not starts and not ends:
start = tickets[0][0]
else:
return None
stack = [start]
reversed_route = []
while stack:
current = stack[-1]
if adjacency[current]:
stack.append(adjacency[current].pop())
else:
reversed_route.append(stack.pop())
route = reversed_route[::-1]
if len(route) != len(tickets) + 1:
return None # A disconnected ticket component was never traversed.
return route
复杂度
构图、度数与 Hierholzer 均 O(V+E) 时间和 O(V+E) 空间；若要求全局字典序最小，需要对每个出边表排序并调整取边顺序，约 O(E log E)。
易错点与追问
容易失分的边界
- 把‘出度为奇数’当作起点条件；正确条件是出度减入度。
- 只核对度数，不检查断开的边组件。
- 用简单 DFS 找一条机场路径，不保证每张边恰好用一次。
- 把同起终点的两张票合并成一条边。
- 无解时输出局部可走的路线却声称用了全部票。
继续深挖
- 若指定从 JFK 出发，平衡回路与非平衡路径分别怎样选起点？
- 若需字典序最小，应怎样安排优先队列或排序边表？
- 若图不断加入新机票，哪些预计算可以复用？
- 为什么先判断弱连通或最终核验边数都能发现断开组件？
