This visualization was AI-generated and may contain inaccuracies. Please verify against the original LeetCode problem (#1136) before relying on it.

Parallel Courses

An interactive visualization of BFS-based topological sort to find the minimum number of semesters needed to take all courses, processing independent courses in parallel each semester.

Topological Sort LeetCode 1136 Medium

The Problem

You are given an integer n, which indicates that there are n courses labeled from 1 to n. You are also given an array relations where relations[i] = [prevCourse, nextCourse] means that course prevCourse must be taken before course nextCourse.

In one semester, you can take any number of courses as long as you have taken all the prerequisites for them in a previous semester.

Return the minimum number of semesters needed to take all courses. If there is no way to take all courses (i.e., there is a cycle in the prerequisites), return -1.

Interactive Visualization

Number of Courses (n)

Relations (pairs)

Preset

Speed:

Course Dependency Graph

Code

fun minimumSemesters(n: Int, relations: Array<IntArray>): Int {    val graph = Array(n + 1) { mutableListOf<Int>() }    val inDegree = IntArray(n + 1)    for ((prev, nextC) in relations) {        graph[prev].add(nextC)        inDegree[nextC]++ }    var queue = ArrayDeque<Int>()    for (i in 1..n) {        if (inDegree[i] == 0)            queue.add(i) }    var semesters = 0    var taken = 0    while (queue.isNotEmpty()) {        semesters++        val nextQueue = ArrayDeque<Int>()        for (idx in 0 until queue.size) {            val course = queue.removeFirst()            taken++            for (neighbor in graph[course]) {                inDegree[neighbor]--                if (inDegree[neighbor] == 0)                    nextQueue.add(neighbor)        }   }   queue = nextQueue }    return if (taken == n) semesters else -1 }

def minimumSemesters(n, relations):    graph = [[] for _ in range(n + 1)]    in_degree = [0] * (n + 1)    for prev, next_c in relations:        graph[prev].append(next_c)        in_degree[next_c] += 1    queue = deque()    for i in range(1, n + 1):        if in_degree[i] == 0:            queue.append(i)    semesters = 0    taken = 0    while queue:        semesters += 1        next_queue = deque()        for _ in range(len(queue)):            course = queue.popleft()            taken += 1            for neighbor in graph[course]:                in_degree[neighbor] -= 1                if in_degree[neighbor] == 0:                    next_queue.append(neighbor)        queue = next_queue    return semesters if taken == n else -1

Status

Press Step or Play to begin.

Log

How It Works

Key Insight

This is a classic application of BFS-based topological sort (Kahn's algorithm). Each "level" of the BFS corresponds to one semester. Courses with no remaining prerequisites (in-degree = 0) can all be taken in the same semester. After taking them, we decrement the in-degree of their dependents, potentially unlocking new courses for the next semester.

The Algorithm

Build the graph and compute in-degrees for each course.
Initialize the queue with all courses that have in-degree 0 (no prerequisites).
Process level by level: Each level = one semester. For every course in the current queue, "take" it and reduce the in-degree of its neighbors. If a neighbor's in-degree drops to 0, add it to the next semester's queue.
Count semesters until the queue is empty.
Check for cycles: If we have taken all n courses, return the semester count. Otherwise, a cycle exists and we return -1.

Why BFS Levels = Semesters

A course can only be taken once all its prerequisites are completed. The earliest a course can be taken is one semester after the last of its prerequisites. BFS naturally groups courses by their earliest possible semester: level 0 has courses with no prerequisites, level 1 has courses whose prerequisites were all in level 0, and so on. This gives the minimum number of semesters.

Complexity

Time O(V + E)

Space O(V + E)

We visit each course (vertex) once and process each prerequisite relation (edge) once. The graph, in-degree array, and queue together use O(V + E) space, where V = n (courses) and E = number of relations.