Advanced Graphs
Using every edge exactly once
A different kind of path problem, with a traversal that looks wrong until you see why it works.
Key idea
Every edge, not every node
So far the searches visited nodes. This problem is about using every edge exactly once, which is a genuinely different constraint and needs a different traversal.
The naive approach is backtracking: try each unused edge, recurse, undo on failure. It is correct and exponential, and it is the answer to give if nothing better comes to mind.
Gotcha
Greedy alone gets stuck
Walking forward and always taking the smallest available unused edge can strand you at a node with no unused edges left while edges elsewhere remain.
That is not a fixable flaw in the ordering; it happens on graphs where some edges must be saved for later. So the algorithm has to be able to recover from getting stuck, without backtracking.
Why it works
Record a node only when it has nothing left
The repair is to build the route in reverse. Walk forward taking edges greedily. When a node has no unused edges left, it is a dead end, so add it to the output and step back. Reverse the whole output at the end.
The invariant that makes it work: a node is only recorded once every edge out of it has been used. So the recorded order is the reverse of a valid route, and reversing it produces one that uses every edge.
Getting stuck is no longer a failure. It is the signal to record and back up, and the walk resumes from wherever there are still unused edges.
On a graph with no choices at all the mechanism is easy to watch. The stack is on the left and the output being built is on the right.
Tip
The case that makes the reversal necessary
Consider a start node with two options, where taking the smaller one leads straight to a dead end while the larger one leads to a cycle that returns. A purely greedy forward walk takes the small option and strands itself with edges still unused.
This algorithm takes it anyway, gets stuck, records that dead end, and backs up. The start node still has its other edge, so the walk continues from there. Reversing at the end places the dead end last, which is correct: it is the only place a route can end.
Draw that three-node case and step through it on paper. It is the fastest way to believe the algorithm, and it is the smallest input on which a purely greedy walk and this one give different answers.
Tip
Sorting descending so that popping gives the smallest
Popping from the end of a list is O(1) and popping from the front is O(n). Sorting the neighbors descending means the cheap pop yields the smallest remaining, which is what a lexicographically smallest route needs.
That is the same list-versus-deque awareness from Unit 0, applied to keep the whole algorithm linear in the edges.
Edge cases
When does such a route exist?
A directed graph has a route using every edge exactly once when it is connected on its edges and the in and out degrees line up: at most one node has one more outgoing edge than incoming, at most one has the reverse, and every other node has them equal.
Most problems guarantee a route exists. Knowing the condition is worth a sentence, and checking it is usually unnecessary work.
Cost
Cost
Every edge is pushed and popped once and every node is recorded once, so O(E) after the sort, and the sort dominates at O(E log E).
Compare with the backtracking version, which can revisit exponentially many partial routes. This is the clearest example in the course of a small structural insight replacing an exponential search with a linear one.
Predict the output: taking the smallest option cheaply
Each node's destinations are stored so that removing the last one always hands back the smallest. Type the three lines it prints.
Reconstruct Itinerary
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.