Chương trình tìm thứ tự sân bay đúng trong Python

Cho danh sách chuyến bay [origin, destination] bị xáo trộn. Tìm thứ tự các sân bay được ghé thăm theo đúng trình tự. Nếu có nhiều lộ trình hợp lệ, trả về theo thứ tự từ điển nhỏ nhất.

Ví dụ: flights = [["Mumbai","Kolkata"],["Delhi","Mumbai"],["Kolkata","Delhi"]] → ['Delhi','Mumbai','Kolkata','Delhi'].

Giải pháp: Hierholzer's algorithm (Eulerian path) trên đồ thị có hướng. Xây danh sách kề, đếm in/out degree, tìm đỉnh bắt đầu (out-in=1), DFS lặp, đảo kết quả.

Ví dụ triển khai

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 = end = None
        for airport in adj_list.keys():
            diff = outs[airport] - ins[airport]
            if diff == 1:
                if start: return
                start = airport
            elif diff == -1:
                if end: return
                end = airport
            elif diff != 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))

Đầu vào

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

Đầu ra

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