Маршрут по всем посадочным

Сложная

Путешественник рассыпал стопку посадочных талонов. Каждый талон passes[i] = [from, to] — это один перелёт из аэропорта from в аэропорт to; аэропорты обозначены трёхбуквенными кодами. Известно, что поездка началась в аэропорту "JFK" и что за неё он слетал по каждому талону ровно один раз. Восстановите маршрут: верните список аэропортов в порядке посещения, начиная с "JFK". Если подходящих маршрутов несколько, верните тот, который идёт раньше по алфавиту, если сравнивать списки по аэропортам слева направо (например, ["JFK", "AMS"] раньше, чем ["JFK", "ATH"]). Гарантируется, что хотя бы один маршрут, использующий все талоны, существует.

Пример 1

passes=[['OSL', 'RIX'], ['JFK', 'DUB'], ['DUB', 'OSL']] → ['JFK', 'DUB', 'OSL', 'RIX']

Из JFK есть только билет в DUB, оттуда — в OSL, затем в RIX. Маршрут единственный.

Пример 2

passes=[['JFK', 'LIS'], ['JFK', 'CPH'], ['CPH', 'JFK'], ['LIS', 'CPH']] → ['JFK', 'CPH', 'JFK', 'LIS', 'CPH']

Подходят два маршрута: JFK, CPH, JFK, LIS, CPH и JFK, LIS, CPH, JFK, CPH. Первый раньше по алфавиту: на втором шаге CPH < LIS.

Пример 3

passes=[['JFK', 'AMS']] → ['JFK', 'AMS']

Ограничения

1 ≤ len(passes) ≤ 300
passes[i] = [from, to], from и to — ровно 3 заглавные латинские буквы
from ≠ to
Маршрут из "JFK" по всем талонам существует

Встречал эту задачу на настоящем собесе?

Решили0

Пробовали0

Отправок0

Принято—

Темы

Depth-First Search Graph Eulerian Circuit

Вход

passes=[['OSL', 'RIX'], ['JFK', 'DUB'], ['DUB', 'OSL']]

Ожидается

['JFK', 'DUB', 'OSL', 'RIX']

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 63 теста на сервере, включая скрытые.