Course Schedule

How it works

Treat each course as a node and each prerequisite as a directed edge. If a course has no prerequisites, it can be taken immediately.

Kahn's Algorithm repeatedly takes courses that have zero prerequisites. When we finish a course, we remove its dependency effect from other courses.

• If all courses can be taken this way - no cycle, return true
• If some courses are never taken - cycle exists, return false

Steps

1. Build a graph and compute indegree (number of prerequisites) for each course.
2. Add all courses with indegree = 0 into a queue.
3. While the queue is not empty:
   • Remove a course from the queue.
   • Mark it as finished.
   • Reduce the indegree of its dependent courses.
   • If any dependent course reaches indegree = 0, add it to the queue.
4. After processing:
   • If finished courses == total courses - return true
   • Else - return false

Complexity

• Time complexity: O(V + E)
• Space complexity: O(V + E)

Where V is the number of courses and E is the number of prerequisites.

Things to watch for

Using a Single Visited Set Instead of Tracking the Current Path

A single visited set marks nodes as seen globally, but cycle detection requires knowing if a node is in the current DFS path. Without tracking the recursion path separately, you may miss cycles or falsely detect them.

Forgetting to Handle Disconnected Components

If you only start DFS from one node, you may miss cycles in disconnected parts of the graph. Always iterate through all courses and run DFS from each unvisited node.

Incorrectly Building the Adjacency List

The prerequisite [a, b] means "to take course a, you must first take course b". Mixing up which course maps to which leads to checking the wrong dependencies and missing or falsely reporting cycles.

from typing import List
from collections import deque

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        indegree = [0] * numCourses
        adj = [[] for i in range(numCourses)]
        for src, dst in prerequisites:
            indegree[dst] += 1
            adj[src].append(dst)

        q = deque()
        for n in range(numCourses):
            if indegree[n] == 0:
                q.append(n)

        finish = 0
        while q:
            node = q.popleft()
            finish += 1
            for nei in adj[node]:
                indegree[nei] -= 1
                if indegree[nei] == 0:
                    q.append(nei)

        return finish == numCourses

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<int> indegree(numCourses, 0);
        vector<vector<int>> adj(numCourses);

        for (auto& pre : prerequisites) {
            indegree[pre[1]]++;
            adj[pre[0]].push_back(pre[1]);
        }

        queue<int> q;
        for (int i = 0; i < numCourses; ++i) {
            if (indegree[i] == 0) {
                q.push(i);
            }
        }

        int finish = 0;
        while (!q.empty()) {
            int node = q.front();
            q.pop();
            finish++;
            for (int nei : adj[node]) {
                indegree[nei]--;
                if (indegree[nei] == 0) {
                    q.push(nei);
                }
            }
        }

        return finish == numCourses;
    }
};