Reconstruct Itinerary

Reconstruct itinerary uses every airline ticket exactly once to build the lexicographically smallest route starting at JFK. Two things make it harder than it first appears. Greedily taking the smallest available destination at each step can strand you. You may reach an airport with no unused tickets while tickets elsewhere remain, and since every ticket must be used, that route is invalid — but you have already committed to it. The correct framing is that tickets are directed edges and the itinerary must use each exactly once. That is an Eulerian path, and the algorithm for it is Hierholzer's: - Follow edges greedily until stuck, then record airports on the way back out of the recursion. The insight is that getting stuck is not a failure. In a graph with an Eulerian path, the airport where you run out of tickets must be the final destination — no other vertex can strand you, because every other vertex has balanced in and out degrees. So appending airports as the recursion unwinds naturally places dead ends at the end of the route. That produces the path in reverse, so reverse it once at the finish. Lexicographic order comes free: always consume the smallest available destination first. A min-heap per airport, or a sorted list consumed from the front, handles that. Duplicate tickets between the same pair must stay as separate entries, since each is a distinct ticket that must be used.

The phrase 'use every ticket/edge exactly once' signals an Eulerian trail rather than ordinary path search. When lexical minimality is also required, order each vertex's outgoing edges while running Hierholzer's algorithm.