পাইথনে সঠিক ক্রমে বিমানবন্দর খুঁজতে প্রোগ্রাম?

ধরুন আমাদের কাছে ফ্লাইটের একটি তালিকা আছে [মূল, গন্তব্য] জোড়া হিসেবে। তালিকা এলোমেলো হয়; আমাদের সঠিক ক্রমে পরিদর্শন করা সমস্ত বিমানবন্দর খুঁজে বের করতে হবে। যদি একাধিক বৈধতালিকা থাকে, তাহলে অভিধানের দিক থেকে সবচেয়ে ছোটটি প্রথমে ফিরিয়ে দিন।

সুতরাং, যদি ইনপুট ফ্লাইটের মত হয় =[["মুম্বাই", "কলকাতা"],["দিল্লি", "মুম্বাই"],["কলকাতা", "দিল্লি"]], তাহলে আউটপুট হবে ['দিল্লি' , 'মুম্বাই', 'কলকাতা', 'দিল্লি']

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব

• ins :=একটি খালি মানচিত্র

• outs :=একটি খালি মানচিত্র

• adj_list :=একটি খালি মানচিত্র

• একটি ফাংশন dfs() সংজ্ঞায়িত করুন। এটি বিমানবন্দর নিতে হবে

• আউটস[এয়ারপোর্ট] শূন্য না হলে, করুন

  • nxt :=adj_list[এয়ারপোর্ট] - আউটস[এয়ারপোর্ট]

    এর আকার

  • আউটস[এয়ারপোর্ট] :=আউটস[এয়ারপোর্ট] - 1

  • উত্তরের শেষে বিমানবন্দর সন্নিবেশ করুন

• সমাধান(), এটি ফ্লাইট নেবে

  নামে একটি পদ্ধতির সংজ্ঞা দিন

• প্রতিটি স্টার্ট এন্ড পেয়ারের জন্য s, e ফ্লাইটে, do

  • adj_list[s]

    -এর শেষে e ঢোকান

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

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

• adj_list-এর সমস্ত মানের তালিকায় প্রতিটি l-এর জন্য, do

  • তালিকাটি সাজান l

• শুরু :=শূন্য, শেষ :=শূন্য

• adj_list-এর সমস্ত কীগুলির তালিকায় প্রতিটি বিমানবন্দরের জন্য, করুন

  • যদি আউট[এয়ারপোর্ট] - ইনস[এয়ারপোর্ট] 1 এর মত হয়, তাহলে

    • যদি শুরু শূন্য না হয়, তাহলে

      • ফেরত

    • শুরু :=বিমানবন্দর

  • অন্যথায় যখন আউট[এয়ারপোর্ট] - ইনস[এয়ারপোর্ট] -1 এর মত হয়, তারপর

    • যদি শেষ শূন্য না হয়, তাহলে

      • ফেরত

    • শেষ :=বিমানবন্দর

  • অন্যথায় যখন আউট[এয়ারপোর্ট] - ইনস[এয়ারপোর্ট] 0 এর মতো নয়, তাহলে

    • ফেরত

• start :=শুরু করুন যদি শুরু শূন্য না হয় অন্যথায় 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']