Свеженькая задача Яндекса Недавно ребята из сообщества algocode.io гоняли на собесы и принесли такую задачку Дан список перелётов tickets, где tickets[i] = [A, B] — перелёт между городами A и B (направление неизвестно). Все перелёты относятся к одному путешествию: • каждый следующий перелёт начинается в городе, где закончился предыдущий • ни один город не посещается дважды • начальный город ≠ конечному Нужно восстановить порядок городов в маршруте. Если есть несколько вариантов — вернуть любой. Пример Ввод: tickets = [["Berlin","Rome"],["Berlin","Dubai"]] Вывод: ["Dubai","Berlin","Rome"] или ["Rome","Berlin","Dubai"] Вся сложность в том, что направления запутаны! Именно на этом валятся Идея решения такая • строим хеш-таблицу graph, где ключ — город отправления, а значение — список городов прибытия (в 2 стороны строим путь) • находим любую вершину, у которой в значении только 1 город — это будет точка старта • обходим граф из стартовой точки, поддерживая visited и не посещая уже отмеченные точки И в итоге получим такое решение from typing import * from collections import defaultdict def route(tickets: List[List[str]]) -> List[str]: # для каждого города храним список городов, с которыми он связан graph = defaultdict(list) for a, b in tickets: graph[a].append(b) graph[b].append(a) # начальный город — тот, у которого ровно одна связь (край маршрута) start = "" for city, neighbors in graph.items(): if len(neighbors) == 1: start = city break # восстанавливаем маршрут, отмечая посещённые города result = [start] visited = {start} for _ in range(len(tickets)): current = result[-1] for neighbor in graph[current]: if neighbor not in visited: visited.add(neighbor) result.append(neighbor) break return result На leetcode не нашел такой задачки Для тех кто уже в сообществе: решить можно самому ТУТ