পাইথনে কোর্সের সময়সূচী

ধরুন আমাদের 0 থেকে numCourses-1 লেবেলযুক্ত মোট numCourses কোর্সগুলি নিতে হবে৷ কিছু কোর্সের পূর্বশর্ত থাকতে পারে, উদাহরণস্বরূপ 0 কোর্স নিতে হলে আমাদের প্রথমে কোর্স 1 নিতে হবে, যা একটি জোড়া ব্যবহার করে প্রকাশ করা হয়:[0,1]। ধরুন এখানে মোট সংখ্যক কোর্স সরবরাহ করা হয়েছে এবং পূর্বশর্ত জোড়ার একটি তালিকা রয়েছে, আমাদের পরীক্ষা করতে হবে আপনার পক্ষে সমস্ত কোর্স শেষ করা সম্ভব কি না?

সুতরাং যদি ইনপুটটি হয় − numCourses =2 এবং পূর্বশর্ত =[[1, 0]], তাহলে ফলাফলটি সত্য হবে, কারণ এখানে মোট 2টি কোর্স নিতে হবে। কোর্স 1 নিতে আমাদের অবশ্যই 0 কোর্স শেষ করতে হবে। তাই এটা সম্ভব।

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

• প্রধান পদ্ধতিতে, এটি numCourses এবং পূর্বশর্তগুলি নেবে:এটি এরকম কাজ করবে −

• যদি পূর্বশর্তের কোনো এন্ট্রি না থাকে, তাহলে সত্য ফেরত দিন

• ভিজিটেড নামে একটি অ্যারে তৈরি করুন, এটি 0 দিয়ে পূরণ করুন এবং এর পরিসীমা numCourses-এর মতোই হয়

• adj_list :=পূর্বশর্ত ব্যবহার করে একটি গ্রাফ তৈরি করুন

• আমি 0 থেকে numCourses এর মধ্যে

  • যদি পরিদর্শন করা হয় [i] মিথ্যা, তাহলে

    • যদি গ্রাফে পরিদর্শন করা নোডের মধ্যে কোন চক্র না থাকে, তাহলে মিথ্যা ফেরত দিন

• প্রত্যাবর্তন সত্য

উদাহরণ

আরো ভালোভাবে বোঝার জন্য নিচের বাস্তবায়নটি দেখি -

class Solution(object):
   def canFinish(self, numCourses, prerequisites):
      if len(prerequisites) == 0:
         return True
      visited = [0 for i in range(numCourses)]
      adj_list = self.make_graph(prerequisites)
      for i in range(numCourses):
         if not visited[i]:
            if not self.cycle(adj_list,visited,i):
               return False
      return True
   def cycle(self,adj_list,visited,current_node = 0):
      if visited[current_node] ==-1:
         return False
      if visited[current_node] == 1:
         return True
      visited[current_node] = -1
      if(current_node in adj_list):
         for i in adj_list[current_node]:
            if not self.cycle(adj_list,visited,i):
               return False
      visited[current_node] = 1
      return True
   def make_graph(self,array):
      adj_list = {}
      for i in array:
         if i[1] in adj_list:
            adj_list[i[1]].append(i[0])
         else:
            adj_list[i[1]] = [i[0]]
      return adj_list
ob = Solution()
print(ob.canFinish(2, [[1,0]]))

ইনপুট

2
[[1,0]]

আউটপুট

true