1743. Restore the Array From Adjacent Pairs — разбор задачи

1. Условие задачи

Турист совершил одно путешествие через несколько городов. Про каждый перелёт известно только, какие два города он соединял, но направление и порядок перелётов потерялись.

Например, пара [2, 3] говорит, что турист летел либо из города 2 в город 3, либо из 3 в 2.

Дано: массив tickets, где каждая пара [A, B] означает прямой перелёт между городами A и B.

Известно:

все билеты относятся к одному непрерывному путешествию;
следующий перелёт начинается там, где закончился предыдущий;
каждый город посещён ровно один раз;
начальный и конечный города различаются;
билеты и города внутри каждой пары могут быть записаны в любом порядке.

Нужно: восстановить города в порядке путешествия. Маршрут можно вернуть в любом направлении: как от начала к концу, так и от конца к началу.

На LeetCode эта же задача сформулирована как восстановление массива уникальных чисел по парам соседних элементов.

Ограничения LeetCode:

число городов N от 2 до 10^5;
билетов всегда N - 1;
номера городов могут быть отрицательными;
корректный маршрут гарантирован.

Пример

tickets = [[2, 1], [3, 4], [3, 2]]

Подходят два ответа:

[1, 2, 3, 4]
[4, 3, 2, 1]

2. Решение

Решение в лоб

Можно взять любой билет, а затем каждый раз просматривать все оставшиеся билеты и искать тот, который продолжает маршрут слева или справа.

В худшем случае для каждого следующего города придётся снова перебирать все билеты. Получится O(N²), что не подходит для N = 10^5.

Главный инсайт: это перемешанный связный список

На первый взгляд задача похожа на обычный граф: города — вершины, билеты — неориентированные рёбра.

Каждый билет [A, B] добавляет связь в обе стороны:

A <-> B

Но по условию все рёбра образуют единственный маршрут без повторного посещения городов:

начало - город - город - ... - конец

Значит, перед нами не произвольный граф с циклами и развилками, а перемешанный двусвязный список.

В обычном двусвязном списке у каждого узла явно подписаны ссылки previous и next. Здесь связи между соседями сохранились, но:

сами узлы перемешались;
порядок связей потерялся;
нигде не указано, какой сосед является previous, а какой next.

У каждого внутреннего города ровно два соседа, а у двух крайних городов — только по одному. Поэтому город, который встречается только в одном билете, является началом или концом маршрута.

Для нас между началом и концом нет разницы. Берём любой край и тем самым сами выбираем направление движения:

город, из которого мы только что пришли, считаем previous;
другого соседа считаем next.

Если начать с противоположного края, previous и next поменяются местами, а мы получим тот же маршрут в обратном порядке. Оба ответа правильные.

После выбора направления структура ведёт себя как обычный односвязный список. Никакой DFS, рекурсии, стека вызовов и множества visited нам не нужно: достаточно пройти цепочку обычным циклом while.

Алгоритм по шагам

Для каждого города создаём список его соседей.
Для билета [A, B] добавляем B в соседи A, а A — в соседи B.
Находим любой город с одним соседом. Это начало или конец маршрута.
Добавляем в ответ найденный край и его единственного соседа.
Пока в ответе меньше N городов, смотрим на два последних элемента маршрута.
Последний элемент — текущий город, предпоследний — previous.
Среди соседей текущего города выбираем того, кто не равен previous, и добавляем его в маршрут.

Визуализация

Возьмём:

tickets = [[2, 1], [3, 4], [3, 2]]

После построения списков соседей получим:

[2]
[1, 3]
[4, 2]
[3]

Города 1 и 4 имеют только по одному соседу, поэтому начать можно с любого. Начнём с 1.

Шаг	previous	Текущий город	next	Маршрут
1	нет	`1`	`2`	`[1, 2]`
2	`1`	`2`	`3`	`[1, 2, 3]`
3	`2`	`3`	`4`	`[1, 2, 3, 4]`

В городе 2 есть соседи 1 и 3. Из 1 мы только что пришли, поэтому 1 — это previous, а 3 — это next. По той же логике из 3 переходим в 4.

Код на Python

from collections import defaultdict
from typing import List


class Solution:
    def restoreArray(self, adjacentPairs: List[List[int]]) -> List[int]:
        # 1. Для каждого города сохраняем его соседей
        neighbors = defaultdict(list)

        for city_a, city_b in adjacentPairs:
            neighbors[city_a].append(city_b)
            neighbors[city_b].append(city_a)

        # 2. Находим начало или конец маршрута
        start = None

        for city in neighbors:
            if len(neighbors[city]) == 1:
                start = city
                break

        # 3. Начинаем с крайнего города и его единственного соседа
        route = [start, neighbors[start][0]]

        # 4. Идём по цепочке как по обычному связному списку
        while len(route) < len(neighbors):
            previous_city = route[-2]
            current_city = route[-1]

            for next_city in neighbors[current_city]:
                if next_city != previous_city:
                    route.append(next_city)
                    break

        return route

Почему алгоритм работает

По условию билеты образуют один маршрут без повторных посещений. Поэтому соответствующая структура является простым путём: у двух крайних вершин по одному соседу, у каждой внутренней — по два.

Мы начинаем с одного из краёв. В каждом внутреннем городе один сосед — это город, из которого мы пришли, а второй — единственное возможное продолжение маршрута. Значит, на каждом шаге алгоритм выбирает правильный следующий город и в итоге восстанавливает всю цепочку.

Если выбрать другой край, получим обратный маршрут, что тоже разрешено условием.

Почему не нужны `visited`, DFS и стек

В произвольном графе множество visited не даёт нам зациклиться, а стек DFS хранит точки возврата: после обхода одной ветки надо вернуться и продолжить другую.

Здесь ветвлений нет. Из внутреннего города можно пойти только:

назад, в previous;
вперёд, в единственного оставшегося соседа.

Возвращаться к развилке никогда не придётся, потому что развилок не существует. Мы просто сдвигаемся от текущего узла к следующему, как при обычной обработке связного списка.

Краевые случаи

Только два города. Обе вершины имеют по одному соседу. Начальный список route уже содержит весь ответ.
Отрицательные номера городов. Они без проблем используются как ключи словаря.
Начали с конечного города. Получим маршрут в обратном направлении, что разрешено условием.
Билеты перемешаны. Их исходный порядок не влияет на построенные связи.
Города внутри билета переставлены. Каждую связь добавляем в обе стороны, поэтому направление пары не важно.
Пустой список билетов. Такой вход невозможен: по условию в маршруте не меньше двух городов.
Цикл или развилка. Такие входы не нужно обрабатывать: условие гарантирует существование одного маршрута без повторных посещений.

3. Сложность алгоритма

Обозначим через N число городов. Тогда билетов будет N - 1.

Построение списков соседей обрабатывает каждый билет один раз: O(N).
Поиск крайнего города просматривает до N городов: O(N).
Цикл добавляет каждый город в маршрут один раз: O(N).
В списках соседей хранятся две записи для каждого билета: O(N).

Итог по времени: O(N).

Итог по памяти: O(N). Сюда входят списки соседей. Возвращаемый массив route тоже содержит N элементов.

Справочно: избыточное решение через DFS

Официальный editorial LeetCode также предлагает рекурсивный DFS. Такое решение естественно приходит в голову, если увидеть в парах рёбра и отнестись к структуре как к настоящему графу.

В общем графе DFS действительно полезен: в вершине может быть несколько ещё не посещённых соседей, а рекурсивный стек запоминает, куда вернуться после каждой ветки. Для защиты от циклов обычно понадобится и множество visited.

Можно написать такой универсальный обход и здесь:

from collections import defaultdict
from typing import List


class Solution:
    def restoreArray(self, adjacentPairs: List[List[int]]) -> List[int]:
        # 1. Строим граф
        neighbors = defaultdict(list)

        for city_a, city_b in adjacentPairs:
            neighbors[city_a].append(city_b)
            neighbors[city_b].append(city_a)

        # 2. Находим начало или конец маршрута
        start = None

        for city in neighbors:
            if len(neighbors[city]) == 1:
                start = city
                break

        route = []
        visited = set()

        # 3. Обходим граф в глубину
        def dfs(current_city: int) -> None:
            visited.add(current_city)
            route.append(current_city)

            for next_city in neighbors[current_city]:
                if next_city not in visited:
                    dfs(next_city)

        dfs(start)
        return route

Для этой задачи код корректен, потому что граф гарантированно является одной цепочкой. Но здесь универсальность DFS только добавляет лишние механизмы:

множество visited занимает дополнительную память;
рекурсия использует стек вызовов;
глубина рекурсии может достигнуть N = 10^5, что в Python приведёт к RecursionError;
ветвлений, ради которых нужен возврат по стеку, в задаче всё равно нет.

Итеративный вариант точнее использует структуру входа: это не произвольный граф, а замаскированный связный список. Поэтому обычный цикл while здесь и проще, и надёжнее.

Вывод

Пары соседних элементов иногда выглядят как рёбра графа, но прежде чем доставать DFS, стоит проверить форму этого графа. В этой задаче он всегда является одной цепочкой — перемешанным связным списком.

Находим любой край, сами назначаем направление previous -> next и проходим маршрут обычным циклом while за O(N).

🐆