Pythonでフライト記録から正しい順序の空港の旅程を復元するプログラム

フライトのリストが [出発地, 目的地] のペア形式で与えられます。このリストはシャッフルされているため、実際に訪問された空港を正しい順序で復元する必要があります。有効な旅程が複数存在する場合は、辞書順で最小のものを優先して返します。

たとえば、入力が flights = [["Mumbai", "Kolkata"], ["Delhi", "Mumbai"], ["Kolkata", "Delhi"]] の場合、出力は ['Delhi', 'Mumbai', 'Kolkata', 'Delhi'] になります。

この問題は、グラフ理論におけるオイラー路（Eulerian Path）、いわゆる「一筆書き経路」を求める問題として捉えることができます。各フライトをグラフの辺、各空港を頂点とみなし、すべての辺をちょうど一度ずつ通る経路を探索します。

解決のためのアプローチ

まず、次の3つのデータ構造を用意します。

• ins: 各空港への到着回数（入次数）を格納するマップ

• outs: 各空港からの出発回数（出次数）を格納するマップ

• adj_list: 各空港から直接行ける目的地の一覧（隣接リスト）

DFS関数の定義

引数として空港を受け取る関数 dfs() を定義します。

• outs[airport] が 0 になるまで、次の処理を繰り返します。

  • nxt := len(adj_list[airport]) - outs[airport]（未使用の辺のインデックスを計算）

  • outs[airport] := outs[airport] - 1

  • dfs(adj_list[airport][nxt]) を再帰的に呼び出す

• ループを抜けたら、ans の末尾に airport を追加します。

solve()メソッドの定義

フライトのリストを受け取る solve() メソッドを定義し、以下の処理を行います。

• flights 内の各ペア (s, e) について:

  • adj_list[s] の末尾に e を追加する

  • outs[s] += 1

  • ins[e] += 1

• adj_list のすべての値（リスト）をソートする（辞書順最小の旅程を得るため）

• start := None、end := None で初期化する

• adj_list のすべてのキー（空港）について:

  • outs[airport] - ins[airport] == 1 の場合:

    • start が既に設定済みなら return（旅程が成立しない）

    • start := airport

  • outs[airport] - ins[airport] == -1 の場合:

    • end が既に設定済みなら return

    • end := airport

  • outs[airport] - ins[airport] != 0 の場合:

    • return（オイラー路が存在せず、旅程を構成できない）

• start が None のまま（オイラー閉路となる場合）は、min(adj_list.keys())、つまり最も辞書順で小さい空港を出発点とする

• ans := 空のリスト

• dfs(start) を呼び出す

• ans を逆順にして返す

最後に、メイン部分から solve(flights) を呼び出します。

Pythonでの実装例

from collections import defaultdict


class Solution:
    def solve(self, flights):
        ins = defaultdict(int)
        outs = defaultdict(int)
        adj_list = defaultdict(list)
        for s, e in flights:
            adj_list[s].append(e)
            outs[s] += 1
            ins[e] += 1
        for l in adj_list.values():
            l.sort()
        start = None
        end = None
        for airport in adj_list.keys():
            if outs[airport] - ins[airport] == 1:
                if start:
                    return
                start = airport
            elif outs[airport] - ins[airport] == -1:
                if end:
                    return
                end = airport
            elif outs[airport] - ins[airport] != 0:
                return
        start = start if start else min(adj_list.keys())
        ans = []

        def dfs(airport):
            while outs[airport]:
                nxt = len(adj_list[airport]) - outs[airport]
                outs[airport] -= 1
                dfs(adj_list[airport][nxt])
            ans.append(airport)

        dfs(start)
        return ans[::-1]


ob = Solution()
flights = [
    ["Mumbai", "Kolkata"],
    ["Delhi", "Mumbai"],
    ["Kolkata", "Delhi"]
]
print(ob.solve(flights))

入力

[["Mumbai", "Kolkata"],
["Delhi", "Mumbai"],
["Kolkata", "Delhi"]]

出力

['Delhi', 'Mumbai', 'Kolkata', 'Delhi']

アルゴリズムのポイント

この手法はHierholzerのアルゴリズムとして知られる古典的な手法に基づいています。出次数と入次数の差を調べることで、旅程の始点（差が +1 の空港）、終点（差が −1 の空港）、またはオイラー閉路（すべての差が 0）であるかを判定できます。隣接リストを事前にソートしておくことで、複数の候補がある場合にも常に辞書順で最小の旅程が選ばれます。DFSで未使用の辺を追跡しながら再帰的に探索するため、フライト数を E とすると O(E log E) の計算量で効率的に正しい旅程を復元できます。