FunctionRacerProblemsRace

Use Every Ticket

HardGraphsPython, JavaScript, TypeScript, Java, C++

Each entry of tickets is [origin, destination]: a ticket for one ride between two towns, in that direction. The same ticket may appear several times, and a ticket may lead from a town back to itself.

You set out from the town start and want to use every ticket exactly once, one ride after another. The tickets are such that this can be done.

Return the towns in the order you visit them, the first being start. If several orders work, return the one that comes first when the lists of town names are compared item by item in alphabetical order.

Example 1

tickets [["ash","bay"],["ash","cove"],["cove","ash"]]
start "ash"
returns ["ash","cove","ash","bay"]

Riding to bay first would leave two tickets that can never be used. So the trip goes to cove, comes back, and ends in bay.

Example 2

tickets [["ash","bay"],["bay","ash"],["ash","cove"],["cove","ash"]]
start "ash"
returns ["ash","bay","ash","cove","ash"]

Both ways round use all four tickets. Going to bay first comes earlier in the alphabet.

Example 3

tickets [["elm","dell"]]
start "elm"
returns ["elm","dell"]

One ticket, one ride.

Constraints

Race itor take your time

Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.

More Graphs problems