Where it runs
1. The problem
You have a shuffled pile of one-way plane tickets. Each ticket is a pair like ["JFK", "MUC"], which means one flight from JFK to MUC. Every ticket must be used exactly once. The trip starts at "JFK". Put the flights in an order that makes one unbroken trip, and list the airports in that order.
Sometimes more than one order works. When you have a choice of where to fly next, take the airport whose code comes first in dictionary order: "ATL" before "SFO", "A" before "B".
Take the tickets [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]. They chain into one trip: ["JFK","MUC","LHR","SFO","SJC"]. Each ticket is used once, and each flight leaves from the airport where the previous one landed.
The earlier graph lessons walked from vertex to vertex and marked the places visited. This task is different: you must go along every edge, which means using every flight exactly once. A walk that goes along every edge exactly once is called an Eulerian path.
This step is part of the paid track
The first 33 steps are open to everyone: lesson, exercise and tests. This one opens with full access. Start with a free account and the free steps.
Create a free accountSee what is includedeulerianPath([["JFK", "ATL"], ["ATL", "BER"], ["ATL", "SFO"], ["SFO", "DEN"], ["DEN", "JFK"], ["JFK", "LAX"], ["LAX", "ATL"]], "JFK")Use all 7 tickets exactly once, starting at JFK. Each airport's tickets are sorted so the smallest destination comes first.
Recognise it
Say these words and it is this pattern
- use every edge exactly once
- reconstruct an itinerary from tickets
- one-stroke drawing / draw without lifting the pen
- walk every road/domino exactly once
- flights or dominoes must chain into one trip
Looks similar, isn't
- Graph BFS / DFS
A traversal has to reach every node. This one has to use every edge.
- Backtracking
Trying routes and undoing them is exponential. This walk never has to take a step back.
- Connected components
Every edge must sit in one component, which is one of the conditions here. Counting groups is not the goal.
- Stack (LIFO)
The stack is what makes the walk work. This page is about when to push onto it.
V nodes and E edges give O(E log E) once the edges are sorted. Without sorting it is O(E).
On LeetCode
Problems that ask you to use every ticket, pair or edge exactly once in one chain. Start at the node with one more outgoing than incoming edge, walk until you are stuck, and put each finished node at the front of the route (Hierholzer).
The lesson task itself. Sort each airport's destinations so the smallest one is tried first.
Each pair is an edge, and the start is the node whose outgoing count beats its incoming count by one, or any node when none does.
Each string of n minus 1 digits is a node and each next digit is an edge, so a path that uses every edge once types every password.