⚡Flashcard Drill➔
NeetCode #609LC-1136MediumGraphsNC Algo100
← Back to All Problems

#609 · #1136 · Parallel Courses(并行课程)

📌 Problem Statement & Constraints

You are given n courses and relations where relations[i] = [a, b] means course a must be taken before b. In one semester you may take any number of courses whose prerequisites are all satisfied. Return the minimum number of semesters, or -1 if impossible. Constraints: 1 <= n <= 5000, 1 <= relations.length <= 5000.

💡 Core Algorithmic Approaches

  1. This is a topological sort where the answer is the number of layers (Kahn's algorithm processed level by level).
  2. Each level contains all courses whose in-degree has just reached 0.
  3. If the total taken is less than n, a cycle exists and the answer is -1.
  4. The layering is what makes it the longest path in the DAG rather than just any topological order.

💻 Benchmark Python3 Implementation

class Solution:
    def minimumSemesters(self, n: int, relations: List[List[int]]) -> int:
        from collections import defaultdict, deque
        g = defaultdict(list)
        indeg = [0] * (n + 1)              # courses are 1-indexed
        for a, b in relations:
            g[a].append(b)
            indeg[b] += 1
        q = deque(i for i in range(1, n + 1) if indeg[i] == 0)
        semesters = 0
        taken = 0
        while q:
            semesters += 1                 # one semester per BFS layer
            for _ in range(len(q)):
                node = q.popleft()
                taken += 1
                for nxt in g[node]:
                    indeg[nxt] -= 1
                    if indeg[nxt] == 0:
                        q.append(nxt)
        return semesters if taken == n else -1

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(V + E): each node and edge is processed once.
💾 Space Complexity
O(V + E) for the graph.

⚠️ Interview Pitfalls & Follow-ups

  • Returning the number of nodes processed: the answer is the number of layers.
  • Not checking the taken count: a cycle leaves some courses untaken.
  • Using 0-indexed arrays: the courses are labelled 1..n.
  • Assuming one course per semester: any number can be taken when prerequisites allow.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Graphs Problems