โปรแกรมค้นหาสนามบินในลำดับที่ถูกต้องใน Python?

สมมติว่าเรามีรายการเที่ยวบินเป็นคู่ [ต้นทาง ปลายทาง] รายการจะถูกสับเปลี่ยน; เราต้องค้นหาสนามบินทั้งหมดที่เข้าเยี่ยมชมในลำดับที่ถูกต้อง หากมีหนังสือเดินทางมากกว่าหนึ่งรายการ ให้ส่งคืนรายการที่เล็กที่สุดก่อน

ดังนั้น หากอินพุตเป็นเหมือนเที่ยวบิน =[["Mumbai", "Kolkata"],["Delhi", "Mumbai"],["Kolkata", "Delhi"] ] ผลลัพธ์จะเป็น ['Delhi' , 'มุมไบ', 'โกลกาตา', 'เดลี']

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้

• ins :=แผนที่ว่างเปล่า

• outs :=แผนที่ว่างเปล่า

• adj_list :=แผนที่ว่างเปล่า

• กำหนดฟังก์ชัน dfs() นี่จะใช้เวลาสนามบิน

• ในขณะที่ outs[airport] ไม่เป็นโมฆะให้ทำ

  • nxt :=ขนาดของ adj_list[airport] - outs[airport]

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

  • ใส่สนามบินที่ส่วนท้ายของ ans

• กำหนดวิธีการที่เรียกว่าแก้ปัญหา () ซึ่งจะใช้เวลาเที่ยวบิน

• สำหรับแต่ละคู่เริ่มต้น s, e ในเที่ยวบิน ทำ

  • ใส่ e ต่อท้าย adj_list[s]

  • ลึกหนาบาง[s] :=ลึก[s] + 1

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

• สำหรับแต่ละ l ในรายการค่าทั้งหมดของ adj_list ให้ทำ

  • เรียงลำดับรายการ l

• start :=null, end :=null

• สำหรับแต่ละสนามบินในรายการคีย์ทั้งหมดของ adj_list ให้ทำ

  • ถ้า outs[airport] - ins[airport] เหมือนกับ 1 แล้ว

    • ถ้าสตาร์ทไม่เป็นโมฆะ

      • กลับ

    • start :=สนามบิน

  • มิฉะนั้นเมื่อ outs[airport] - ins[airport] เหมือนกับ -1 ดังนั้น

    • ถ้าจุดสิ้นสุดไม่เป็นโมฆะ

      • กลับ

    • end :=สนามบิน

  • มิฉะนั้นเมื่อ outs[airport] - ins[airport] ไม่เหมือนกับ 0 แล้ว

    • กลับ

• start :=start ถ้า start ไม่เป็นโมฆะ มิฉะนั้น ค่าต่ำสุดของคีย์ทั้งหมดของ adj_list

• ans :=รายการใหม่

• dfs(เริ่ม)

• ย้อนกลับของ ans

• จากเมธอดหลัก เรียก แก้ไข(เที่ยวบิน)

ตัวอย่าง

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