Решение задачи 332. Reconstruct Itinerary
Нам дана пачка авиабилетов некого пассажира, начинающего свое путешествие в Нью-Йорке (JFK). Билеты представлены в виде двумерного массива tickets, где tickets[i] = [fromi, toi]. from и to - строки с кодами аэропортов ИАТА. От нас требуется восстановить маршрут пассажира, использовав все билеты строго по одному разу. Если возможны несколько вариантов маршрута, то нужно вывести лексикографически минимальный. Авторы гарантируют, что на вход будут поступать только те данные, для которых такой маршрут существует.
Маршрутную сеть, которую охватывают представленные билеты, нетрудно представить в виде ориентированного графа, где вершинами будут аэропорты, а ребрами - билеты. Нам нужно так обойти этот граф, чтобы после посещения всех вершин у нас не осталось ребер, по которым не был совершен переход.
То есть, задача сводится к поиску Эйлерова пути, но с условием, что, если в графе есть циклы, по ним нужно будет пройти в порядке лексикографического возрастания возможных путей. Граф, как нам гарантируют авторы задачи, будет представлять собой либо Эйлеров цикл, либо Эйлеров путь. То есть, в графе могут быть либо ровно две вершины, входящая степень которых отличается от исходящей на 1, либо таких вершин не будет вообще. При этом у одной из вершин будет больше исходящая степень, а у другой - входящая. Эти вершины, если они есть, будут начальной и конечной точками маршрута.
Для обхода графа с посещением всех вершин подходит поиск в глубину. Но его нужно будет немного отрегулировать. Традиционно поиск в глубину обходит все вершины графа, заходя в каждую строго один раз, отмечая посещенные. Это нужно, чтобы избежать зацикливания, если в графе есть циклы. Таким образом, традиционный поиск в глубину не будет совершать переход по ребрам, ведущим в уже посещенные вершины. Нам это не подходит - нужно как раз использовать все ребра, а вот на повторное посещение вершин никакого ограничения нет. В пути возможны различные циклы, условие лишь в том, чтобы пройти их в таком порядке, чтобы итоговый маршрут по сумме всех строковых обозначений аэропортов оказался лексикографически минимальным.
Выход есть. Нужно поставить поиску в глубину задачу пройти по каждому ребру по одному разу. Для того, чтобы избежать повторного прохождения по уже использованному ребру (билету) и зацикливания, мы будем после перехода по ребру удалять его из графа, тем самым исключая повторное использование ребра и разрывая возможный цикл. Для того, чтобы маршрут был лексикографически минимальным, нам при каждом переходе нужно выбирать лексикографически минимальное ребро. Алгоритмически это жадный выбор. Ребра для каждой вершины при этом должны быть отсортированы.
Выполняя указанный алгоритм, мы будем проходить по каждому ребру графа, удаляя его. Для каждой вершины этот алгоритм будет выполняться рекурсивно, то есть процедура обработки всех ребер будет однотипна для любой вершины графа, а порядок их обработки на прямом ходу рекурсии будет отражать последовательность путевых точек итогового маршрута. Для каждой вершины алгоритм завершится, когда у нее не останется исходящих ребер. На этом этапе мы добавляем вершину в итоговый путь.
Так как первой в итоговый путь в этом случае попадет самая дальняя точка маршрута, а последним будет добавлен начальный аэропорт "JFK", итоговый маршрут нужно будет перевернуть.
Алгоритм может быть реализован рекурсивно. Первой обрабатываемой вершиной по условию должен быть "JFK". Можно также переписать алгоритм итеративно, стек вызовов при этом заменит std::stack.
Мое решение написано итеративно, а для поддержания отсортированного порядка обработки ребер использует std::priority_queue.