用Python编写查找正确排序的机场程序？

假设我们有一个航班列表，其中包含[起点，终点]对。列表已混合; 我们必须查找所有已访问的机场的正确顺序。如果有多个有效的行程，则首先返回词典序最小的行程。

因此，如果输入如下flights = [[“Mumbai”, “Kolkata”],[“Delhi”, “Mumbai”],[“Kolkata”, “Delhi”] ]，则输出将为[‘Delhi’，’Mumbai’，’Kolkata’，’Delhi’]

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

• ins：一个空映射

• outs：一个空映射

• adj_list：一个空映射

• 定义一个函数dfs() 。这将取决于机场。

• 当outs [机场]不为空时，执行以下操作

  • nxt：adj_list [机场]的大小 – outs [机场]

  • 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进行排序
• start：null，end：null

• 对于adj_list所有键的列表中的每个机场，请执行以下操作

  • 如果outs [机场] – ins [机场]与1相同，则
    • 如果开始不为空，则

    • 返回

    • 开始=机场

  • 否则，当outs [机场] – ins [机场]与-1相同时 ，则

    • 如果结束不为空，则

    • 返回

    • end = airport

  • 否则，当outs [机场] – ins [机场]不等于0时，则

    • 返回

• 如果开始不为null，则开始=开始，否则是adj_list键的最小值

• 答案=一个新的列表

• 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))

输入

[["孟买", "加尔各答"],
["德里", "孟买"],
["加尔各答", "德里"]] 

输出

['德里'， '孟买'， '加尔各答'， '德里']