Pinterest 旅行机票重建：起点未知的有向 Euler 路径

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 训练版每张有向票恰好使用一次，允许重复的 (from,to) 作为不同票；需输出一条覆盖全部票的城市序列。
• 若多条合法路线，取字典序最小；若存在 Euler 回路而没有唯一入度 0 起点，从有出边的最小城市开始。无路线返回空列表，空票也返回空列表。
• 若现场实际要求只走一条简单链、任意 DFS 路径或不必用完票，则不能直接套用本文。

解题路线

1. 统计每个城市的出入度；有向 Euler trail 的起点应满足 out−in=1，终点满足 in−out=1，其余平衡。若所有点平衡，选非零出度的最小城市。
2. 每个城市的下一站放小根堆，用 Hierholzer：能走票时压入栈，走不动时弹出城市到逆序答案。
3. 最后反转答案，并核对长度是票数+1、相邻边多重集与原票一致；这同时排除虽满足度数但分离的无效图。
4. 用最多 7 张票的随机小图穷举每张票的选择顺序，独立比较字典序最小解。

手动走一遍

票 [A→B,B→C,C→A,A→D]：A 的出度比入度大 1，D 的入度比出度大 1，路线 A,B,C,A,D。若同一 A→B 出现两张，要消耗两张，不能用 set 去重。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

"""Lexicographically smallest Euler trail using every directed ticket once."""

from collections import Counter, defaultdict
from heapq import heapify, heappop


def reconstruct_itinerary(tickets: list[tuple[str, str]]) -> list[str]:
    if not tickets:
        return []
    outgoing = Counter(start for start, _ in tickets)
    incoming = Counter(end for _, end in tickets)
    vertices = set(outgoing) | set(incoming)
    starts = [city for city in vertices if outgoing[city] - incoming[city] == 1]
    ends = [city for city in vertices if incoming[city] - outgoing[city] == 1]
    if len(starts) > 1 or len(ends) > 1 or len(starts) != len(ends):
        return []
    if any(abs(outgoing[city] - incoming[city]) > 1 for city in vertices):
        return []
    start = starts[0] if starts else min(outgoing)
    adjacency = defaultdict(list)
    for city, destination in tickets:
        adjacency[city].append(destination)
    for destinations in adjacency.values():
        heapify(destinations)
    route = []
    stack = [start]
    while stack:
        city = stack[-1]
        if adjacency[city]:
            stack.append(heappop(adjacency[city]))
        else:
            route.append(stack.pop())
    route.reverse()
    if len(route) != len(tickets) + 1:
        return []
    if Counter(zip(route, route[1:])) != Counter(tickets):
        return []
    return route

复杂度

E 张票、V 个机场，建堆 O(E)，每张票出堆 O(log 出度)，总 O(E log E) 时间；堆、栈和答案 O(E+V) 空间。若不要求字典序，邻接列表弹末尾可做到 O(E+V)。

易错点与追问

容易失分的边界

• 只选入度 0 城市，遇 Euler 回路就无法开始。
• 简单 DFS 找到终点就返回，遗漏机票。
• 把重复票去重，错误地缩短路线。
• 只看出入度而不验证全票被消耗。

继续深挖

• 若要求固定从 JFK 出发，怎样改变起点验证？
• 若不要求字典序，复杂度能降到多少？
• 机场数量很大但票只涉及少数机场时，索引如何构建？