C++で訪問都市の正しい順序（旅程）を復元するプログラム

出発空港と到着空港のペア [from, to] で表される航空券のリストが与えられたとします。このとき、すべての航空券を一度ずつ使用する旅程を正しい順序で復元する必要があります。すべての航空券は KLK から出発する一人の旅行者が所有しているため、旅程は必ず KLK から始まります。

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

解決のためのアプローチ

この問題は、グラフ理論におけるオイラー路（Eulerian Path）を求める問題として捉えることができます。各空港を頂点、航空券を有向辺とみなし、深さ優先探索（DFS）を用いて経路を構築します。具体的な手順は以下の通りです。

• 結果を格納する配列 ret と、隣接リストを表すマップ graph を定義します。
• 空港名を引数に取るメソッド visit を定義します。
• visit 内では、graph[airport] のサイズが 0 になるまで次を繰り返します。
  • x := graph[airport] の先頭要素を取得する。
  • graph[airport] からその先頭要素を削除する。
  • visit(x) を再帰的に呼び出す。
• ループを抜けたら、現在の空港名を ret の末尾に追加します。

メイン処理の流れ

• i を 0 からチケット配列のサイズまでループし、u := tickets[i][0]、v := tickets[i][1] として、v を graph[u] に挿入します。
• 出発地である visit("KLK") を呼び出します。
• 最後に ret を逆順にして返します。これは、DFS の帰りがけ順で空港を記録しているためです。

なお、マップの値に multiset を使うことで、同じ区間の航空券が複数あっても正しく扱え、かつ辞書順に小さい到着地から優先的に訪問できます。

それでは、理解を深めるために実際の実装を見てみましょう。

サンプルコード

#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("KLK");
        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"},{"KLK","MUC"},{"SFO","SJC"},{"LHR","SFO"}};
    print_vector(ob.findItinerary(v));
}

入力

{{"MUC","LHR"},{"KLK","MUC"},{"SFO","SJC"},{"LHR","SFO"}}

出力

[KLK, MUC, LHR, SFO, SJC]

まとめ

このアルゴリズムの計算量は、航空券の数を E とすると O(E log E) となります。これは、各航空券（辺）を multiset への挿入・削除で 1 回ずつ処理し、multiset の操作に log の係数がかかるためです。DFS の帰りがけ順に結果を記録して最後に反転させることで、行き止まりになった経路も含めてすべての航空券を消費する正しい旅程を効率的に復元できる点がポイントです。