Путешественник совершил серию прямых перелётов. Сохранились только пары городов:
известно, что между ними был перелёт, но не известны ни направление, ни порядок.
Все перелёты — части одного путешествия, ни один город не посещён дважды, город
старта отличается от конечного. Восстановите маршрут — последовательность городов.
// Leg — перелёт между двумя городами, направление неизвестно.
type Leg = [2]string
// BuildRoute возвращает города в порядке следования.
func BuildRoute(legs []Leg) []string
Примеры
[(Lisbon, Oslo)] → [Lisbon Oslo]
[(Lisbon, Oslo), (Lisbon, Dublin)] → [Dublin Lisbon Oslo]
[(Prague, Oslo), (Lisbon, Oslo), (Lisbon, Dublin)] → [Dublin Lisbon Oslo Prague]
[] → []
Направление восстановить нельзя, поэтому подходит любой из двух концов в
качестве старта: [Oslo Lisbon Dublin] для второго примера тоже верный ответ.
Ограничения
0 ≤ len(legs) ≤ 2·10⁵, вход гарантированно образует одну простую цепочку.- Ожидаемая сложность — O(N) по времени. Сортировка или поиск по всем перелётам
на каждом шаге не проходят по времени.
Устно: как изменится решение, если билеты направленные (from → to)?