Course Schedule

mediumGraphs: Topological Sort & Union-Find61 stepsJava · Python · C++

Courses are nodes and prerequisites are edges; you can finish them all only if the graph has no cycle. Kahn's algorithm repeatedly takes a course with no remaining prerequisites. If every course gets taken, there's no cycle.

▶ Watch the animated trace

Traced input: numCourses = 4, prerequisites = [[1, 0], [2, 0], [3, 1], [3, 2]] → true. Original problem: neetcode.io/problems/course-schedule

Complexity

BestO(V + E)

AverageO(V + E)

WorstO(V + E)

SpaceO(V + E)

Each course and prerequisite is processed once.

Key idea

In-degree = number of unfinished prerequisites.
Start with every course whose in-degree is 0.
Taking a course lowers its dependants' in-degrees; any that hit 0 join the queue.
If a cycle exists, its courses never reach in-degree 0.

Common mistakes

Getting the edge direction backwards: [a, b] means b must come before a.
DFS cycle detection needs three colours (unvisited, in progress, done); two aren't enough.

Solution

Java

boolean canFinish(int n, int[][] prerequisites) {
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
    int[] indegree = new int[n];
    for (int[] p : prerequisites) {
        adj.get(p[1]).add(p[0]);
        indegree[p[0]]++;
    }
    Queue<Integer> queue = new ArrayDeque<>();
    for (int i = 0; i < n; i++) if (indegree[i] == 0) queue.offer(i);
    int taken = 0;
    while (!queue.isEmpty()) {
        int c = queue.poll();
        taken++;
        for (int next : adj.get(c)) {
            if (--indegree[next] == 0) queue.offer(next);
        }
    }
    return taken == n;
}

Python

def canFinish(n: int, prerequisites: List[List[int]]) -> bool:
    adj = [[] for _ in range(n)]
    indegree = [0] * n
    for a, b in prerequisites:
        adj[b].append(a)
        indegree[a] += 1
    queue = deque(i for i in range(n) if indegree[i] == 0)
    taken = 0
    while queue:
        c = queue.popleft()
        taken += 1
        for nxt in adj[c]:
            indegree[nxt] -= 1
            if indegree[nxt] == 0: queue.append(nxt)
    return taken == n

C++

bool canFinish(int n, vector<vector<int>>& prerequisites) {
    vector<vector<int>> adj(n);
    vector<int> indegree(n);
    for (auto& p : prerequisites) {
        adj[p[1]].push_back(p[0]);
        indegree[p[0]]++;
    }
    queue<int> q;
    for (int i = 0; i < n; i++) if (indegree[i] == 0) q.push(i);
    int taken = 0;
    while (!q.empty()) {
        int c = q.front(); q.pop();
        taken++;
        for (int next : adj[c]) {
            if (--indegree[next] == 0) q.push(next);
        }
    }
    return taken == n;
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
Simple cycle Each course waits for the other.	`numCourses = 2, prerequisites = [[1, 0], [0, 1]]`	`false`
No prerequisites Every course starts with in-degree 0.	`numCourses = 3, prerequisites = []`	`true`
Self loop A course that requires itself can never start.	`numCourses = 1, prerequisites = [[0, 0]]`	`false`
Cycle in one component 0 and 1 finish, but 2 and 3 are stuck.	`numCourses = 4, prerequisites = [[1, 0], [2, 3], [3, 2]]`	`false`