Coding: DFS Through All Cities

HardPython

Problem

Booking's flight search can represent available segments as directed flights between cities. Given a starting city and a list of flight tickets, reconstruct an itinerary that uses every ticket exactly once and visits every city appearing in the tickets.

If multiple valid itineraries exist, return the lexicographically smallest sequence of city codes. Return an empty list if no such itinerary exists.

Formal Specification

Implement find_itinerary(flights, start), where flights is a list of two-element lists [from_city, to_city], and start is the starting city code. Return a list of city codes containing exactly len(flights) + 1 entries, or [] when reconstruction is impossible. Duplicate flights are distinct tickets and must each be used once.

The itinerary must follow the direction of every flight. A route that uses all tickets but leaves some tickets disconnected from the starting city is invalid.

Constraints

1 <= len(flights) <= 2 * 10^5
Each flight contains exactly two city codes
City codes are non-empty uppercase strings
Duplicate flights are allowed
Return the lexicographically smallest valid itinerary

Function Signature

def find_itinerary(flights, start):

If multiple valid itineraries exist, return the lexicographically smallest sequence of city codes. Return an empty list if no such itinerary exists.

Formal Specification

The itinerary must follow the direction of every flight. A route that uses all tickets but leaves some tickets disconnected from the starting city is invalid.