C++で航空券リストから旅程を再構築する方法（DFS・ヒールホルツァーアルゴリズム）

問題概要

出発空港と到着空港のペア [from, to] で表される航空券のリストが与えられたとき、すべての航空券を使い切る形で旅程を正しい順序に再構築します。すべての航空券は JFK 空港から旅を始める一人の旅行者のものであるため、旅程は必ず「JFK」から始まる必要があります。

たとえば、入力が [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]] の場合、出力は ["JFK", "MUC", "LHR", "SFO", "SJC"] となります。

解法のアプローチ

この問題は、グラフ理論における「オイラー路」を求める問題として捉えることができます。各空港を頂点、航空券を辺とみなすと、「すべての辺（航空券）をちょうど一度ずつ通る経路」を見つけることが目的になります。これにはヒールホルツァー（Hierholzer）のアルゴリズムに基づく深さ優先探索（DFS）が有効です。

具体的には、以下の手順で解きます。

• 結果を格納する配列 ret と、隣接リストを表すマップ graph を定義します。
• 空港名を引数に取るメソッド visit を定義します。
• graph[airport] のサイズが 0 でない限り、次を繰り返します。
  • x := graph[airport] の先頭要素
  • graph[airport] から先頭要素を削除
  • visit(x) を再帰的に呼び出す
• ループを抜けたら、airport を ret に追加します（帰りがけ順の記録）。
• メイン処理では、i を 0 からチケット配列のサイズまでループさせます。
  • u := tickets[i][0]、v := tickets[i][1] とし、v を graph[u] に挿入します。
• 出発地なので visit("JFK") を呼び出します。
• 最後に ret を反転させて返します。

ここで multiset を使用するのがポイントです。同じ行き先への複数のチケットも重複なく管理でき、さらに要素が自動的に辞書順でソートされるため、「利用可能なチケットがある場合は常に辞書順で最小の空港を選ぶ」という条件を自然に満たせます。また、帰りがけ順（post-order）で空港を記録し、最後にリストを反転することで、行き止まりから順に辿った正しい旅程が得られます。

計算量

• 時間計算量：O(E log E)（E は航空券の枚数。multiset への挿入・削除が対数時間のため）
• 空間計算量：O(E)（グラフの隣接リストと再帰スタック分）

C++での実装例

理解を深めるために、以下の実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
    cout << "[";
    for(int i = 0; i<v.size(); i++){
        cout << v[i] << ", ";
    }
    cout << "]"<<endl;
}
class Solution {
    public:
    vector <string> ret;
    map < string, multiset <string> > graph;
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        for(int i = 0; i < tickets.size(); i++){
            string u = tickets[i][0];
            string v = tickets[i][1];
            graph[u].insert(v);
        }
        visit("JFK");
        reverse(ret.begin(), ret.end());
        return ret;
    }
    void visit(string airport){
        while(graph[airport].size()){
            string x = *(graph[airport].begin());
            graph[airport].erase(graph[airport].begin());
            visit(x);
        }
        ret.push_back(airport);
    }
};
main(){
    Solution ob;
    vector<vector<string>> v = {{"MUC","LHR"},{"JFK","MUC"},{"SFO","SJC"},{"LHR","SFO"}};
    print_vector(ob.findItinerary(v));
}

入力

[["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]

出力

[JFK, MUC, LHR, SFO, SJC]