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

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

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

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

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

courses := n
visited := आकार n+1 की एक सरणी, और इसे false से भरें
queue := एक नई सूची
graph := n+1 उप-सूचियों की एक सूची
in_degree := आकार n+1 की एक सरणी, और इसे 0 से भरें
relations में प्रत्येक i के लिए, करें
- i[1] को graph[i[0]] के अंत में सम्मिलित करें
- in_degree[i[1]] := in_degree[i[1]] + 1
semester := 1
i को 1 से n+1 तक की रेंज में, करें
- यदि in_degree[i] शून्य है, तो
  - i को queue के अंत में सम्मिलित करें
  - visited[i] := True
semester := 1
courses := courses - queue का आकार
जब तक queue खाली नहीं है और courses शून्येतर है, करें
- current_size := queue का आकार
- जब तक current_size शून्येतर है, करें
  - current_course := queue[0]
  - queue से पहला तत्व हटाएं
  - current_size := current_size - 1
  - graph[current_course] में प्रत्येक i के लिए, करें
    - in_degree[i] := in_degree[i] - 1
    - यदि i विज़िट नहीं किया गया है और in_degree[i] शून्य है, तो
      - courses := courses - 1
      - i को queue के अंत में सम्मिलित करें
      - visited[i] := True
- semester := semester + 1
semester लौटाएं यदि courses 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         semester = 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]]