Начало — город отправления, который нигде не встречается как прибытие. Постройте отображение отправление→прибытие и последовательно пройдите от начала до отсутствия следующего билета.
Как восстановить маршрут из билетов без разветвлений
Начало — город отправления, который нигде не встречается как прибытие. Постройте отображение отправление→прибытие и последовательно пройдите от начала до отсутствия следующего билета.
Короткий ответ
Что ответить на собеседовании
Подробный разбор
Ответ с пояснениями
Условие
Билеты образуют один направленный путь без циклов и повторов: Москва→Казань, Омск→Томск, Казань→Омск. Как найти начало, конец и полный маршрут?
Ответ
Начало — город отправления, который нигде не встречается как прибытие. Постройте отображение отправление→прибытие и последовательно пройдите от начала до отсутствия следующего билета.
В примере начало Москва, конец Томск, маршрут Москва→Казань→Омск→Томск. Проверяйте, что использованы все билеты и нет двух исходящих рёбер из одного города. Для разветвлений или циклов этот простой контракт не подходит: может потребоваться другая постановка, например эйлеров путь.