पायथन में पाठ्यक्रम अनुसूची

मान लीजिए कि कुल संख्या पाठ्यक्रम हैं जिन्हें हमें लेना है, जिन्हें 0 से numCourses-1 तक लेबल किया गया है। कुछ पाठ्यक्रमों में पूर्वापेक्षाएँ हो सकती हैं, उदाहरण के लिए पाठ्यक्रम 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