Parallel Courses

Parallel Courses is a topological-sort problem in disguise. The twist over a plain topo sort: you may take many courses at once, so the real question is not the order — it is how few rounds you need.

The slow way first

You could try taking courses one at a time in a valid order — a normal topological sort — and count steps. But that ignores the gift the problem hands you: courses with no remaining prerequisites can be taken together. Doing them one per semester would massively over-count. We need to take a whole layer of unblocked courses each round.

The question to ask: which courses can I take right now? Exactly the ones with no unmet prerequisite. Take all of them, see what that unlocks, repeat.

The idea: peel the DAG one level at a time

This is Kahn's algorithm run in levels (a layered BFS). For each course track its in-degree — the number of prerequisites still pointing at it. Every course with in-degree 0 can be taken now; that batch is one semester. Taking it relaxes (decrements) the in-degree of its dependents, which unlocks the next batch.

The key insight: the number of BFS rounds is the minimum number of semesters. And if some course never reaches in-degree 0, it sits in a prerequisite cycle — impossible, so we return -1.

Walk through it

Step through the animation. Courses 1 and 2 start with in-degree 0, so they are semester 1. Finishing them unlocks 3 and 4 (semester 2), which unlocks 5 (semester 3). Three rounds, three semesters. The semester counter on the right ticks once per BFS layer.

Pseudocode

build graph and in-degree from prerequisites
queue = every course with in-degree 0
taken = 0, semesters = 0
while queue is not empty:
    semesters += 1               # one whole layer = one semester
    next_queue = empty
    for each course u in queue:
        taken += 1
        for each dependent v of u:
            in-degree[v] -= 1
            if in-degree[v] == 0:
                add v to next_queue
    queue = next_queue
return semesters if taken == n else -1   # -1 means a cycle

The Python solution

def min_semesters(n, prerequisites):
    graph = {c: [] for c in range(1, n + 1)}
    indeg = {c: 0 for c in range(1, n + 1)}
    for u, v in prerequisites:
        graph[u].append(v)
        indeg[v] += 1
 
    queue = [c for c in graph if indeg[c] == 0]
    taken = semesters = 0
    while queue:
        semesters += 1
        nxt = []
        for u in queue:
            taken += 1
            for v in graph[u]:
                indeg[v] -= 1
                if indeg[v] == 0:
                    nxt.append(v)
        queue = nxt
    return semesters if taken == n else -1

• graph is an adjacency list; indeg[v] counts the prerequisites still pointing at v.
• queue starts with every course that has no prerequisite (in-degree 0).
• Each iteration of the while loop is one semester — that is why semesters += 1 happens once per round, not once per course.
• The inner loop takes the entire current batch at once and relaxes every dependent.
• A dependent that hits in-degree 0 joins nxt, the next semester batch.
• taken == n confirms we took every course. If not, some course was stuck in a cycle, so we return -1.

Complexity

Every course is queued exactly once and every prerequisite edge is relaxed exactly once, so the whole algorithm is linear in the size of the graph.

When this pattern shows up

Practice