Дан набор пар городов:

Условие

""" Дан набор пар городов:

• между каждой парой городов сотрудник совершил прямой перелёт;
• информация, в каком направлении был совершён перелёт, утеряна.
• также утерян порядок перелетов.

Известно, что все указанные перелёты относятся к одному путешествию. Каждый следующий перелёт сотрудник начинал из того города, в котором закончил предыдущий. Никакой город не был посещён сотрудником дважды. Город начала путешествия также отличается от конечной точки. Выведите города в порядке следования по маршруту. Существует два возможных ответа, подойдёт любой.

Примеры: [("Москва", "Белград")] -> ["Москва", "Белград"] [("Москва", "Белград"), ("Москва", "Ереван")] -> ["Ереван", "Москва", "Белград"]

Flight = tuple[str, str]

def get_route(flights: list[Flight]) -> list[str]: ...

Ответ

Постройте неориентированный граф по парам городов, начните с вершины степени 1 и каждый раз идите к соседу, отличному от предыдущего. Обратный маршрут также корректен.

def get_route(flights):
    if not flights:
        return []
    graph = {}
    for a, b in flights:
        graph.setdefault(a, []).append(b)
        graph.setdefault(b, []).append(a)
    start = next(city for city, neighbors in graph.items() if len(neighbors) == 1)
    route = []
    previous, current = None, start
    while current is not None:
        route.append(current)
        following = next((city for city in graph[current] if city != previous), None)
        previous, current = current, following
    return route

Решение опирается на гарантии условия: один связный путь без повторных городов. Время и память O(n). Для недоверенного входа отдельно проверяют степени, связность, отсутствие циклов и повторных рёбер.