Hints — p70 Reconstruct Itinerary

Hint 1. Recognize the problem: use every ticket (edge) exactly once = Eulerian path in a directed multigraph. Named algorithm: Hierholzer’s.

Hint 2. Naive greedy (“always pick lex-smallest next destination”) FAILS. Counterexample: JFK can go to ATL (dead end) or KUL (long subtour); greedy picks ATL, gets stuck. Need a smarter approach.

Hint 3. Hierholzer’s trick: DFS but append nodes in POST-ORDER (after exploring all outgoing edges), then reverse the route at the end. Dead-end subtours naturally end up in the correct (last) position.

Hint 4. For lex-smallest: store each node’s destinations in a min-heap; always pop the smallest available destination. Each pop removes that ticket from consideration.

Hint 5. Iterative form (production-clean):

stack = ["JFK"]; route = []
while stack:
    if heap[stack[-1]]:
        stack.append(heappop(heap[stack[-1]]))
    else:
        route.append(stack.pop())
return route[::-1]

If stuck: see solution.py.