Topological Sort - Parallel Courses (Minimum Semesters)
Consider the following Python code implementing the optimal approach for minimum semesters. Given
n = 3 and relations = [[1,3],[2,3]], what is the value of semester returned by the function?from collections import deque, defaultdict
def min_semesters_optimal(n, relations):
graph = defaultdict(list)
indegree = [0] * (n + 1)
for u, v in relations:
graph[u].append(v)
indegree[v] += 1
queue = deque([i for i in range(1, n + 1) if indegree[i] == 0])
semester = 0
processed = 0
while queue:
semester += 1
for _ in range(len(queue)):
course = queue.popleft()
processed += 1
for nei in graph[course]:
indegree[nei] -= 1
if indegree[nei] == 0:
queue.append(nei)
return semester if processed == n else -1
print(min_semesters_optimal(3, [[1,3],[2,3]]))