Reconstruct Itinerary
hardTime: O(E log E)Space: O(V+E)
Signals to notice
use all tickets exactly oncefind Eulerian pathlexicographically smallest itinerary
Brute force first
Try all permutations of tickets — O(n!). Each ordering checked for validity.
The key insight
Hierholzer's algorithm: DFS greedily choosing the lexicographically smallest neighbor. When stuck, add the current airport to the result in reverse. O(E log E) for sorting adjacency lists.
What must stay true
By always choosing the smallest destination and building the result when backtracking (stuck = no more edges), you construct the lexicographically smallest Eulerian path in reverse.
Easy way to go wrong
Not building the result in reverse — Hierholzer's adds cities when backtracking from dead ends, so the path is assembled from the end backward.