Algorithms & Data Structureshard

Reconstruct Itinerary II

You are given flight tickets as [from, to] pairs and a starting airport. The itinerary uses every ticket exactly once, starting at start; when several are valid, it is the lexicographically smallest one.

Return whether that itinerary ever revisits an airport it has already been through.

tickets = [["MUC","LHR"], ["JFK","MUC"], ["SFO","SJC"], ["LHR","SFO"]], start = "JFK"
itinerary JFK, MUC, LHR, SFO, SJC                     => false

tickets = [["JFK","SFO"], ["JFK","ATL"], ["SFO","ATL"], ["ATL","JFK"], ["ATL","SFO"]], start = "JFK"
itinerary JFK, ATL, JFK, SFO, ATL, SFO                => true

Up to 300 tickets; airport codes are three uppercase letters. The tickets always form at least one valid itinerary from start.

Hints

Hint 1

First reconstruct the itinerary: greedy DFS over reverse-sorted adjacency lists, appending an airport to the route when it has no tickets left, then reversing (Hierholzer's algorithm).

Hint 2

The question is about the finished route: any airport appearing twice is a revisit — a set comparison, not another graph algorithm.

Hints

Asked at