Pythonで正しい順序で空港を見つけるプログラム？

[出発地、目的地]のペアとしてフライトのリストがあるとします。リストはシャッフルされます。訪問したすべての空港を正しい順序で見つける必要があります。複数の有効なものがある場合は、辞書式順序で最も小さいものを最初に返します。

したがって、入力がflights =[["Mumbai"、 "Kolkata"]、["Delhi"、 "Mumbai"]、["Kolkata"、 "Delhi"]]の場合、出力は['Delhi' 、'ムンバイ'、'コルカタ'、'デリー']

これを解決するために、次の手順に従います

• ins：=空のマップ

• outs：=空のマップ

• adj_list：=空のマップ

• 関数dfs（）を定義します。これは空港になります

• outs [airport]がnullでない場合は、実行してください

  • nxt：=adj_list[airport]のサイズ-outs[airport]

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

  • ansの最後に空港を挿入

• Solve（）というメソッドを定義します。これにはフライトが必要です

• フライトの開始と終了のペアごとに、実行します

  • adj_list [s]

    の最後にeを挿入します

  • outs [s]：=outs [s] + 1

  • ins [e]：=ins [e] + 1

• adj_listのすべての値のリスト内の各lについて、実行します

  • リストを並べ替えるl

• start：=null、end：=null

• adj_listのすべてのキーのリストにある空港ごとに、実行します

  • outs [airport]-ins [airport]が1と同じ場合、

    • nullでない場合は、

      • 戻る

    • 開始：=空港

  • それ以外の場合、outs [airport] --ins [airport]が-1と同じ場合、

    • endがnullでない場合、

      • 戻る

    • 終了：=空港

  • それ以外の場合、outs [airport] --ins [airport]が0と同じでない場合、

    • 戻る

• start：=startがnullでない場合はstart、それ以外の場合はadj_listのすべてのキーの最小値

• ans：=新しいリスト

• dfs（start）

• ansの逆を返す

• メインメソッドからsolve（flights）を呼び出します

例

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']