Reconstruct Itinerary

def findItinerary(tickets):
    graph = defaultdict(list)
    for a, b in sorted(tickets, reverse=True):
        graph[a].append(b)      # smallest goes last
    route = []
    def visit(a):
        while graph[a]:
            visit(graph[a].pop())   # smallest
        route.append(a)             # no tickets left
    visit("JFK")
    return route[::-1]

Reconstruct Itinerary. You're handed a pile of plane tickets, each from one airport to another. Starting at J F K, use every ticket exactly once, and return the trip that comes first alphabetically.

Four tickets make one chain: J F K, Munich, London, San Francisco, San Jose. Five tickets can be used up in three different trips. Compared stop by stop, J F K, Atlanta, J F K comes first, so it wins.

Why not always take the smallest ticket? From J F K, Kuala Lumpur beats Narita, but then we're stuck, with two tickets unused. The naive fix backtracks: try tickets in order, and undo on dead ends. That can take exponential time.

The fix: using every ticket once is an Eulerian path, and Hierholzer's algorithm finds it. Still take the smallest ticket, but write an airport down only when it has no tickets left, filling the scroll from the end. Kuala Lumpur gets stuck first, so it lands last, and the Narita loop fills in before it.

In code, sort each airport's tickets. Visit an airport: while it has tickets, pop the smallest and visit there. When it runs out, append it to the route. Reverse at the end.

Try the five tickets. From J F K: Atlanta, J F K, San Francisco, Atlanta, San Francisco. San Francisco is out of tickets, so it's written last. Unwinding, each airport runs out too, and the scroll fills backward.

With E tickets, sorting costs order E log E time, and each ticket is used once. The lists, the route and the recursion take order E space.

Smallest ticket first, write it down when stuck, then reverse. That's Reconstruct Itinerary.