计划在Python中以正确的顺序查找机场？

假设我们有一个航班列表，分别是[原点，目的地]对。列表被打乱了；我们必须找到以正确顺序访问的所有机场。如果有多个有效行程，请首先返回按字典顺序最小的行程。

因此，如果输入就像flights = [[“” Mumbai“，” Kolkata“]，[” Delhi“，” Mumbai“]，[” Kolkata“，” Delhi“]]]，那么输出将是['Delhi' ，“孟买”，“加尔各答”，“德里”]

为了解决这个问题，我们将按照以下步骤

• ins：=一个空的映射

• 出局：=空映射

• adj_list：=一个空的映射

• 定义一个功能dfs()。这将带机场

• 而outs [airport]不为null时，执行

• nxt：= adj_list [airport]的大小-outs [airport]

• outs [机场]：= outs [机场]-1

• 在ans结尾处插入机场

• 定义一个名为的方法solve()，这将进行

• 对于航班中的每个出发端对s，e

• 在adj_list [s]的末尾插入e

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

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

• 对于adj_list所有值列表中的每个l，执行

• 排序列表l

• 开始：= null，结束：= null

• 对于adj_list所有键列表中的每个机场，执行

• 返回

• 如果end不为null，则

• 结束：=机场

• 返回

• 如果开始不为空，则

• 开始：=机场

• 返回

• 如果outs [airport]-ins [airport]与1相同，则

• 否则，当outs [airport]-ins [airport]与-1相同时，则

• 否则，当outs [airport]-ins [airport]不等于0时，则

• start：=如果start不为null，则开始，否则adj_list的所有键的最小值

• ans：=一个新列表

• dfs（开始）

• 返回ans的反向

• 从主要方法中调用solve（航班）

示例

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