Где применяется
1. Задача
У тебя перемешанная стопка билетов в одну сторону. Каждый билет это пара вроде ["JFK", "MUC"], то есть один рейс из JFK в MUC. Каждый билет надо использовать ровно один раз. Поездка начинается в "JFK". Расставь рейсы так, чтобы получилась одна непрерывная поездка, и перечисли аэропорты по порядку.
Иногда верных порядков несколько. Когда есть выбор, куда лететь дальше, бери аэропорт с наименьшим кодом в словарном порядке: "ATL" раньше "SFO", "A" раньше "B".
Возьми билеты [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]. Они складываются в одну поездку: ["JFK","MUC","LHR","SFO","SJC"]. Каждый билет использован один раз, и каждый рейс вылетает из того аэропорта, куда прилетел предыдущий.
В прошлых уроках про графы мы ходили от вершины к вершине и отмечали посещённые места. Здесь задача другая: пройти по каждому ребру, то есть использовать каждый рейс ровно один раз. Обход, который проходит по каждому ребру ровно один раз, называется эйлеровым путём.
Этот шаг из платной части
Бесплатные шаги в начале курса (их 33) открыты всем: урок, задача и тесты. Этот шаг открывается с полным доступом. Начни с бесплатного аккаунта и бесплатных шагов.
Завести бесплатный аккаунтПосмотреть, что входитeulerianPath([["JFK", "ATL"], ["ATL", "BER"], ["ATL", "SFO"], ["SFO", "DEN"], ["DEN", "JFK"], ["JFK", "LAX"], ["LAX", "ATL"]], "JFK")Нужно использовать все 7 билетов ровно по разу, начиная с JFK. Билеты каждого аэропорта отсортированы, первым идёт наименьший пункт назначения.
Как узнать
Эти слова в условии значат этот паттерн
- использовать каждое ребро ровно один раз
- восстановить маршрут по билетам
- рисунок одним росчерком / не отрывая ручку
- пройти каждую дорогу/домино ровно один раз
- рейсы или домино должны соединиться в одну поездку
Похоже, но не то
- Обход графа BFS / DFS (Graph BFS / DFS)
Обходу нужно достичь каждой вершины. Здесь нужно использовать каждое ребро.
- Бэктрекинг (Backtracking)
Пробовать маршруты и откатывать их это экспонента. Этот обход шагов назад не делает.
- Компоненты связности (Connected components)
Все рёбра обязаны лежать в одной компоненте, и это одно из условий. Но считать группы здесь не цель.
- Стек (LIFO) (Stack (LIFO))
Стек это то, на чём обход держится. Эта страница про то, когда в него класть.
V вершин и E рёбер дают O(E log E) вместе с сортировкой рёбер. Без сортировки это O(E).
На LeetCode
Задачи, где каждый билет, пару или ребро нужно использовать ровно один раз в одной цепочке. Начни с вершины, у которой исходящих рёбер на одно больше, чем входящих, иди, пока не застрянешь, и ставь каждую законченную вершину в начало маршрута (Хирхольцер).
Это сама задача урока. Отсортируй направления каждого аэропорта, чтобы первым пробовать наименьшее.
Каждая пара это ребро, а старт это вершина, у которой исходящих на одно больше, чем входящих, или любая, если такой нет.
Каждая строка из n минус 1 цифр это вершина, каждая следующая цифра это ребро, и путь по всем рёбрам ровно один раз набирает все пароли.