पायथन में समानांतर पाठ्यक्रम

मान लीजिए कि एन पाठ्यक्रम हैं, और इन्हें 1 से एन तक लेबल किया गया है। हमने एक संबंध सरणी भी दी है, जहां संबंध [i] =[एक्स, वाई], पाठ्यक्रम एक्स और पाठ्यक्रम वाई के बीच एक पूर्वापेक्षा संबंध का प्रतिनिधित्व कर रहा है। तो, इसका मतलब है पाठ्यक्रम X का अध्ययन पाठ्यक्रम Y से पहले किया जाना है।

एक सेमेस्टर में हम कितने भी पाठ्यक्रमों का अध्ययन कर सकते हैं, जब तक कि हम जिस पाठ्यक्रम का अध्ययन कर रहे हैं, उसके लिए सभी पूर्वापेक्षाओं का अध्ययन कर लिया है। हमें सभी पाठ्यक्रमों का अध्ययन करने के लिए आवश्यक न्यूनतम सेमेस्टर की संख्या ज्ञात करनी होगी। और यदि सभी पाठ्यक्रमों का अध्ययन करने का कोई तरीका नहीं है, तो -1 लौटें।

इसलिए, यदि इनपुट एन =3, संबंध =[[1,3], [2,3]] जैसा है, तो आउटपुट 2 होगा क्योंकि पहले सेमेस्टर में, पाठ्यक्रम 1 और 2 का अध्ययन किया जाता है। दूसरे सेमेस्टर में, पाठ्यक्रम 3 का अध्ययन किया जाता है।

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

• पाठ्यक्रम :=n

• विज़िट किया गया :=आकार n+1 की एक सरणी, और इसे असत्य से भरें

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

• ग्राफ़ :=n+1 उपन्यासकारों की सूची

• in_degree :=आकार n+1 की एक सरणी, और इसे 0 से भरें

• संबंधों में प्रत्येक के लिए, करते हैं

  • ग्राफ़ के अंत में i[1] डालें[i[0]]

  • in_degree[i[1]] :=in_degree[i[1]] + 1

• सेमेस्टर :=1

• 1 से n+1 की श्रेणी में i के लिए, करें

  • अगर in_degree[i] शून्य है, तो

    • कतार के अंत में i डालें

    • दौरा किया [i] :=सच

• सेमेस्टर :=1

• पाठ्यक्रम:=पाठ्यक्रम - कतार का आकार

• जबकि कतार खाली नहीं है और पाठ्यक्रम शून्य नहीं है, करें

  • current_size :=कतार का आकार

  • जबकि current_size गैर-शून्य है, करें

    • current_course :=कतार[0]

    • कतार से पहला तत्व हटाएं

    • current_size :=current_size - 1

    • ग्राफ़ में प्रत्येक i के लिए[current_course], करें

      • in_degree[i] :=in_degree[i] - 1

      • अगर मैं नहीं गया और in_degree[i] शून्य है, तो

        • कोर्स :=कोर्स - 1

        • कतार के अंत में i डालें

        • विज़िट किया गया[i]:=सच

  • सेमेस्टर:=सेमेस्टर + 1

• वापसी सेमेस्टर अगर पाठ्यक्रम 0 है अन्यथा -1

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

class Solution(object):
   def minimumSemesters(self, n, relations):
      courses = n
      visited = [False for i in range(n+1)]
      queue = []
      graph = [[] for i in range(n+1)]
      in_degree = [0 for i in range(n+1)]
      for i in relations:
         graph[i[0]].append(i[1])
         in_degree[i[1]]+=1
      semeseter = 1
      for i in range(1,n+1):
         if not in_degree[i]:
            queue.append(i)
            visited[i] = True
         semester = 1
         courses -= len(queue)
         while queue and courses:
            current_size = len(queue)
            while current_size:
               current_course = queue[0]
               queue.pop(0)
               current_size-=1
               for i in graph[current_course]:
                  in_degree[i]-=1
                  if not visited[i] and not in_degree[i]:
                     courses-=1
                     queue.append(i)
                  visited[i]=True
            semester+=1
         return semester if not courses else -1

ob = Solution()
print(ob.minimumSemesters(3,[[1,3],[2,3]]))

इनपुट

3, [[1,3],[2,3]]

आउटपुट

-1