Reconstruct Itinerary

Problem

You are given a list of flight tickets, each a pair [from, to] of airport codes. All tickets belong to one traveller who starts at "JFK" and must use every ticket exactly once. Reconstruct the itinerary as the list of airports visited in order. If several complete itineraries exist, return the one that is lexicographically smallest when read as a sequence of airport codes. You may assume at least one valid itinerary exists.

• There are at most a few hundred tickets.
• Airport codes are three uppercase letters.
• The same [from, to] pair may appear more than once (multiple identical tickets).

Examples

• tickets = [["ORD","LGA"],["JFK","ORD"],["DEN","OAK"],["LGA","DEN"]] → ["JFK","ORD","LGA","DEN","OAK"]. Only one order uses every ticket.
• tickets = [["JFK","BOS"],["JFK","MIA"],["BOS","MIA"],["MIA","JFK"],["MIA","BOS"]] → ["JFK","BOS","MIA","JFK","MIA","BOS"]. ["JFK","MIA","BOS","JFK","MIA","BOS"] also uses every ticket but is lexicographically larger.
• tickets = [["JFK","SEA"],["JFK","AUS"],["AUS","JFK"]] → ["JFK","AUS","JFK","SEA"]. Greedily flying to AUS first (it sorts before SEA) strands you with an unused ticket, so the smallest complete itinerary is not the greedy one.

Hints

1. Model airports as nodes and tickets as directed edges. "Use every ticket once" is a classic property of a walk through a graph; which one?
2. Always taking the alphabetically smallest unused ticket can dead-end with tickets left over. What should happen to a node when you get stuck there?
3. Hierholzer's algorithm: DFS taking the smallest outgoing edge each time, and add an airport to the answer only when it has no unused outgoing edges left. The reversed post-order is the itinerary.