Problem context and objectives
Mission briefing
Realm network architect · Routes have costs, dependencies, and unreliable bridges
Choose the next frontier that preserves the route guarantee: The Ticket Trail.
One locally tempting edge can invalidate the whole journey.
How you win
- 1Recognize when Hierholzer Eulerian itinerary matches the clues
- 2Keep this true after every move: every removed ticket appears exactly once in the reversed postorder route
- 3Reach the result within O(E log E)
Rules and pressure
- Target cost: O(E log E)
- State rule: every removed ticket appears exactly once in the reversed postorder route
Lesson 1 of 3
Live algorithm trace
Hierholzer Eulerian itinerary
Complete execution1 of 6
JFK
start
ATL
JFK
SFO
ATL
SFO
Store each departure's destinations so popping chooses the lexical minimum.
1
store destinations in reverse lexical order2
dfs(airport)3
while an outgoing ticket remains4
remove the smallest destination and recurse5
append airport after exhausting edges6
reverse the postorder routeJFK = SFO,ATLATL = SFO,JFKSFO = ATL
Truth to preserve / Cost target
Truth to preserve
every removed ticket appears exactly once in the reversed postorder route
Cost target
O(E log E)
Always consume the lexicographically smallest outgoing ticket, but append an airport only after it has no tickets left. Reversing this postorder trail splices cycles into one Eulerian path.
Your call · What should guide every step of this algorithm?