पायथन में हवाई अड्डों को सही क्रम में खोजने का कार्यक्रम?

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

इसलिए, यदि इनपुट फ्लाइट्स =[["मुंबई", "कोलकाता"], ["दिल्ली", "मुंबई"], ["कोलकाता", "दिल्ली"]] की तरह है, तो आउटपुट ['दिल्ली' होगा। , 'मुंबई', 'कोलकाता', 'दिल्ली']

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

• ins :=एक खाली नक्शा

• outs :=एक खाली नक्शा

• adj_list :=एक खाली नक्शा

• फ़ंक्शन को परिभाषित करें dfs() । यह हवाई अड्डे ले जाएगा

• जबकि outs[airport] खाली नहीं है, करें

  • अगला:=adj_list का आकार [हवाई अड्डा] - बाहरी [हवाई अड्डे]

  • बाहरी [हवाई अड्डे]:=बाहरी [हवाई अड्डे] - 1

  • उत्तर के अंत में हवाई अड्डा डालें

• हल () नामक एक विधि को परिभाषित करें, यह उड़ानें लेगा

• प्रत्येक स्टार्ट एंड जोड़ी के लिए, ई उड़ानों में, करें

  • adj_list[s]

    . के अंत में e डालें

  • बहिष् [s] :=outs[s] + 1

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

• adj_list के सभी मानों की सूची में प्रत्येक l के लिए, करें

  • सूची को क्रमबद्ध करें l

• प्रारंभ:=शून्य, अंत:=शून्य

• adj_list की सभी कुंजियों की सूची में प्रत्येक हवाई अड्डे के लिए, करें

  • अगर outs[airport] - ins[airport] 1 के समान है, तो

    • यदि प्रारंभ शून्य नहीं है, तो

      • वापसी

    • प्रारंभ:=हवाई अड्डा

  • अन्यथा जब outs[airport] - ins[airport] -1 के समान हो, तब

    • अगर अंत शून्य नहीं है, तो

      • वापसी

    • अंत:=हवाई अड्डा

  • अन्यथा जब outs[airport] - ins[airport] 0 के समान नहीं है, तब

    • वापसी

• प्रारंभ:=प्रारंभ करें यदि प्रारंभ शून्य नहीं है अन्यथा adj_list की सभी कुंजियों में से न्यूनतम

• उत्तर :=एक नई सूची

• dfs(शुरू)

• उत्तर के विपरीत लौटें

• मुख्य विधि से कॉल हल करें(उड़ानें)

उदाहरण

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