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

Giả sử chúng ta có một danh sách các chuyến bay là các cặp [điểm xuất phát, điểm đến]. Danh sách bị xáo trộn; chúng tôi phải tìm kiếm tất cả các sân bay đã đến theo đúng thứ tự. Nếu có nhiều hơn một danh sách hợp lệ, trước tiên hãy trả lại những từ nhỏ nhất về mặt từ vựng.

Vì vậy, nếu đầu vào giống như các chuyến bay =[["Mumbai", "Kolkata"], ["Delhi", "Mumbai"], ["Kolkata", "Delhi"]], thì đầu ra sẽ là ['Delhi' , 'Mumbai', 'Kolkata', 'Delhi']

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau

• ins:=một bản đồ trống

• outs:=một bản đồ trống

• adj_list:=một bản đồ trống

• Định nghĩa một hàm dfs (). Điều này sẽ đưa đến sân bay

• trong khi outs [airport] không phải là null, hãy thực hiện

  • nxt:=size of adj_list [airport] - outs [airport]

  • outs [sân bay]:=outs [sân bay] - 1

  • chèn sân bay vào cuối ans

• Xác định một phương thức có tên là giải quyết (), phương thức này sẽ thực hiện các chuyến bay

• cho mỗi cặp bắt đầu kết thúc s, e trong chuyến bay, thực hiện

  • chèn e vào cuối adj_list [s]

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

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

• đối với mỗi l trong danh sách tất cả các giá trị của adj_list, thực hiện

  • sắp xếp danh sách l

• start:=null, end:=null

• cho mỗi sân bay trong danh sách tất cả các khóa của adj_list, hãy làm

  • nếu outs [airport] - in [airport] bằng 1 thì

    • nếu bắt đầu không null, thì

      • trở lại

    • start:=airport

  • ngược lại khi outs [airport] - in [airport] giống -1 thì

    • nếu end không null thì

      • trở lại

    • end:=sân bay

  • ngược lại khi outs [airport] - in [airport] không giống 0 thì

    • trở lại

• start:=start nếu start không null nếu không thì tối thiểu tất cả các khóa của adj_list

• ans:=một danh sách mới

• dfs (bắt đầu)

• trả về đảo ngược của ans

• Từ phương thức chính, hãy gọi giải quyết (chuyến bay)

Ví dụ

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

Đầu vào

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

Đầu ra

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