पायथन में हवाई अड्डों को सही क्रम में ढूंढने का प्रोग्राम

मान लीजिए हमारे पास उड़ानों की एक सूची है जैसे [origin, destination] जोड़े। सूची शफल है; हमें सही क्रम में देखे गए सभी हवाई अड्डों को ढूंढना है। यदि एक से अधिक वैध यात्रा कार्यक्रम हैं, तो लेक्सिकोग्राफिक रूप से सबसे छोटे को पहले लौटाएं।

उदाहरण के लिए, यदि इनपुट है flights = [["Mumbai", "Kolkata"],["Delhi", "Mumbai"],["Kolkata", "Delhi"] ], तो आउटपुट होगा ['Delhi', 'Mumbai', 'Kolkata', 'Delhi']

इसे हल करने के लिए, हम निम्न चरणों का पालन करेंगे

• ins := एक खाली मैप
• outs := एक खाली मैप
• adj_list := एक खाली मैप
• एक फ़ंक्शन dfs() परिभाषित करें। यह airport लेगा
• जब तक outs[airport] null नहीं है, करें
  • nxt := adj_list[airport] का आकार - outs[airport]
  • outs[airport] := outs[airport] - 1
  • airport को ans के अंत में डालें
• solve() नामक एक विधि परिभाषित करें, यह flights लेगा
• प्रत्येक start end जोड़ी s, e के लिए flights में, करें
  • e को adj_list[s] के अंत में डालें
  • outs[s] := outs[s] + 1
  • ins[e] := ins[e] + 1
• adj_list के सभी मानों की सूची में प्रत्येक l के लिए, करें
  • सूची l को सॉर्ट करें
• start := null, end := null
• adj_list की सभी कुंजियों की सूची में प्रत्येक airport के लिए, करें
  • यदि outs[airport] - ins[airport] 1 के समान है, तो
    • यदि start null नहीं है, तो
      • लौटें
    • start := airport
  • अन्यथा जब outs[airport] - ins[airport] -1 के समान है, तो
    • यदि end null नहीं है, तो
      • लौटें
    • end := airport
  • अन्यथा जब outs[airport] - ins[airport] 0 के समान नहीं है, तो
    • लौटें
• start := start यदि start null नहीं है अन्यथा adj_list की सभी कुंजियों का न्यूनतम
• ans := एक नई सूची
• 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))

इनपुट

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

आउटपुट

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