LeetCode 207 Course Schedule: Cycle Detection with Topological Sort

Course Schedule is the problem that introduces most people to topological sorting, and it's one of the most common graph questions in interviews. The story is about university courses, but the structure is everywhere in software: build systems compiling modules in dependency order, package managers installing libraries, spreadsheets recalculating cells, and workflow schedulers running DAGs of jobs. In each case, a cycle means "impossible", and the question is how to detect it efficiently.

This guide covers both standard algorithms with dry runs and code in Python, C++ and Java, explains the subtle reason DFS needs three states, extends to Course Schedule II, and lists the follow-ups interviewers like. For a broader tour of the technique, see the topological sort guide.

The Problem and the Graph Model

There are numCourses courses labelled 0 to n − 1. You're given prerequisites, where [a, b] means you must take course b before course a. Return true if you can finish all courses.

Constraints: 1 ≤ numCourses ≤ 2000, 0 ≤ prerequisites.length ≤ 5000, all pairs distinct. So V ≤ 2000 and E ≤ 5000, and any O(V + E) algorithm is instant.

From prerequisites to a directed graph

Each course is a node. For each pair [a, b], add a directed edge b → a, read as "b unlocks a". The question "can I take every course in some order that respects every edge?" is exactly "does this graph have a topological order?", and a directed graph has one if and only if it has no directed cycle (it's a DAG).

Why cycles are exactly the obstacle: on a cycle, every course needs another course on the cycle first, so none can be taken first. Conversely, if there's no cycle, some course has no unmet prerequisites (otherwise you could keep walking backwards along prerequisite edges forever in a finite graph, which forces a repeat, which is a cycle). Take it, remove it, and repeat. That argument is Kahn's algorithm.

Approach 1: Kahn's Algorithm (BFS Topological Sort)

The in-degree of a course is the number of prerequisites it still needs. Courses with in-degree 0 can be taken right now.

1. Build the adjacency list (b → a) and the in-degree of every course.
2. Seed a queue with every course whose in-degree is 0.
3. Process: pop a course, count it as taken, and for each course it unlocks, decrement that course's in-degree. If it drops to 0, push it.
4. Decide: if the number taken equals numCourses, return true. Otherwise some courses never reached in-degree 0, which only happens when they're on a cycle or depend on one.

from collections import deque
from typing import List

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        adj = [[] for _ in range(numCourses)]
        indegree = [0] * numCourses
        for course, pre in prerequisites:
            adj[pre].append(course)          # pre unlocks course
            indegree[course] += 1

        q = deque(i for i in range(numCourses) if indegree[i] == 0)
        taken = 0
        while q:
            u = q.popleft()
            taken += 1
            for v in adj[u]:
                indegree[v] -= 1
                if indegree[v] == 0:
                    q.append(v)
        return taken == numCourses

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

import java.util.*;

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) adj.add(new ArrayList<>());
        int[] indegree = new int[numCourses];
        for (int[] p : prerequisites) {
            adj.get(p[1]).add(p[0]);
            indegree[p[0]]++;
        }
        Deque<Integer> q = new ArrayDeque<>();
        for (int i = 0; i < numCourses; i++)
            if (indegree[i] == 0) q.add(i);
        int taken = 0;
        while (!q.isEmpty()) {
            int u = q.poll();
            taken++;
            for (int v : adj.get(u))
                if (--indegree[v] == 0) q.add(v);
        }
        return taken == numCourses;
    }
}

Kahn's Algorithm Dry Run

Example A: a DAG

numCourses = 4, prerequisites = [[1,0], [2,0], [3,1], [3,2]]. Edges: 0→1, 0→2, 1→3, 2→3. Initial in-degrees: [0, 1, 1, 2].

taken = 4 = numCourses, so true. The pop order 0, 1, 2, 3 is a valid schedule.

Example B: a cycle hidden behind valid courses

numCourses = 4, prerequisites = [[1,0], [2,1], [1,2], [3,0]]. Edges: 0→1, 1→2, 2→1, 0→3. In-degrees: [0, 2, 1, 1].

The queue empties with taken = 2 < 4, so false. Courses 1 and 2 still have in-degree 1 each, from each other: that's the cycle. A useful fact: after Kahn's finishes, the nodes with non-zero in-degree are exactly those on a cycle or reachable from one.

Approach 2: DFS with Three Colors

DFS explores one path as deep as it goes. A cycle exists exactly when DFS finds an edge pointing back to a node that's still on the current path (a "back edge"). To know what's on the current path, give each node one of three states:

import sys
from typing import List

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        sys.setrecursionlimit(10000)          # a chain of 2000 courses recurses 2000 deep
        adj = [[] for _ in range(numCourses)]
        for course, pre in prerequisites:
            adj[pre].append(course)

        WHITE, GRAY, BLACK = 0, 1, 2
        color = [WHITE] * numCourses

        def has_cycle(u: int) -> bool:
            color[u] = GRAY
            for v in adj[u]:
                if color[v] == GRAY:
                    return True               # back edge
                if color[v] == WHITE and has_cycle(v):
                    return True
            color[u] = BLACK
            return False

        return not any(color[i] == WHITE and has_cycle(i) for i in range(numCourses))

class Solution {
    vector<vector<int>> adj;
    vector<int> color;          // 0 = white, 1 = gray, 2 = black

    bool hasCycle(int u) {
        color[u] = 1;
        for (int v : adj[u]) {
            if (color[v] == 1) return true;
            if (color[v] == 0 && hasCycle(v)) return true;
        }
        color[u] = 2;
        return false;
    }
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        adj.assign(numCourses, {});
        color.assign(numCourses, 0);
        for (const auto& p : prerequisites) adj[p[1]].push_back(p[0]);
        for (int i = 0; i < numCourses; ++i)
            if (color[i] == 0 && hasCycle(i)) return false;
        return true;
    }
};

Dry run on Example B

Edges 0→1, 1→2, 2→1, 0→3. Start DFS at 0.

1. Enter 0: color[0] = gray. Path: 0.
2. Edge 0→1: 1 is white, enter it. color[1] = gray. Path: 0 → 1.
3. Edge 1→2: 2 is white, enter it. color[2] = gray. Path: 0 → 1 → 2.
4. Edge 2→1: 1 is gray, so it's on the current path. Back edge, cycle 1 → 2 → 1. Return true all the way up.

The outer loop is needed because the graph may be disconnected: a cycle in a component not reachable from course 0 must still be found. Every white node gets its own DFS start.

Recursion depth

A chain 0 → 1 → 2 → … → 1999 recurses 2,000 deep. Python's default limit is about 1,000, so the recursive Python version needs the raised limit shown above (or an iterative DFS with an explicit stack). C++ and Java handle 2,000 frames comfortably. Kahn's algorithm sidesteps the issue entirely, which is one reason many people default to it.

Why a Simple Visited Set Isn't Enough

In an undirected graph, "I reached a visited node that isn't my parent" means a cycle. In a directed graph, that rule breaks, and it's worth understanding both ways it breaks because interviewers love to ask.

Mistake 1: one global visited set, "seen before means cycle"

Take the diamond 0→1, 0→2, 1→3, 2→3 from Example A. DFS goes 0 → 1 → 3, finishes, backs up to 0, goes to 2, then sees 3 is visited. With "visited means cycle", it reports a cycle. But there isn't one: 3 was reached by two different paths, which is perfectly fine in a DAG. Black (finished) nodes must not trigger a cycle.

Mistake 2: one global visited set, "seen before means skip"

Now the opposite: treat visited nodes as safe and skip them. Then a back edge to a node on the current path is also skipped, and real cycles are missed. In Example B, when DFS at 2 sees 1 already visited, it would skip it and happily report "no cycle".

The three-color scheme resolves both: gray (on the path) means cycle, black (finished) means safe to skip. An equivalent formulation uses two boolean arrays, visited and onStack; gray is "visited and on stack", black is "visited and not on stack".

Course Schedule II (LeetCode 210): Return the Order

Same input, but return one valid order of all courses, or an empty array if impossible.

With Kahn's algorithm

The order in which courses are dequeued is already a topological order: a course is enqueued only after all its prerequisites have been dequeued.

from collections import deque
from typing import List

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        adj = [[] for _ in range(numCourses)]
        indegree = [0] * numCourses
        for course, pre in prerequisites:
            adj[pre].append(course)
            indegree[course] += 1
        q = deque(i for i in range(numCourses) if indegree[i] == 0)
        order = []
        while q:
            u = q.popleft()
            order.append(u)
            for v in adj[u]:
                indegree[v] -= 1
                if indegree[v] == 0:
                    q.append(v)
        return order if len(order) == numCourses else []

With DFS: reverse post-order

When DFS finishes a node (turns it black), everything that depends on it, meaning everything reachable from it, has already finished. So the finish order lists dependents before prerequisites. Reverse it to get a valid schedule.

class Solution {
    vector<vector<int>> adj;
    vector<int> color, finishOrder;

    bool dfs(int u) {                       // returns false if a cycle is found
        color[u] = 1;
        for (int v : adj[u]) {
            if (color[v] == 1) return false;
            if (color[v] == 0 && !dfs(v)) return false;
        }
        color[u] = 2;
        finishOrder.push_back(u);
        return true;
    }
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        adj.assign(numCourses, {});
        color.assign(numCourses, 0);
        finishOrder.clear();
        for (const auto& p : prerequisites) adj[p[1]].push_back(p[0]);
        for (int i = 0; i < numCourses; ++i)
            if (color[i] == 0 && !dfs(i)) return {};
        reverse(finishOrder.begin(), finishOrder.end());
        return finishOrder;
    }
};

On Example A, DFS from 0 visits 1, then 3 (finishes 3), finishes 1, visits 2 (3 is black), finishes 2, finishes 0. Finish order: 3, 1, 2, 0. Reversed: 0, 2, 1, 3, which is valid. Kahn's gave 0, 1, 2, 3; both are correct, since topological orders aren't unique.

Bonus: report the cycle itself

A product-flavoured follow-up: "If the schedule is impossible, tell the student which courses form the loop." DFS makes this easy because the gray nodes are the current path.

def find_cycle(num_courses, prerequisites):
    adj = [[] for _ in range(num_courses)]
    for course, pre in prerequisites:
        adj[pre].append(course)
    color = [0] * num_courses
    path = []                                # current DFS path (the gray nodes)

    def dfs(u):
        color[u] = 1
        path.append(u)
        for v in adj[u]:
            if color[v] == 1:
                return path[path.index(v):] + [v]   # slice of the path from v back to v
            if color[v] == 0:
                cycle = dfs(v)
                if cycle:
                    return cycle
        path.pop()
        color[u] = 2
        return None

    for i in range(num_courses):
        if color[i] == 0:
            cycle = dfs(i)
            if cycle:
                return cycle
    return []

# find_cycle(4, [[1,0],[2,1],[1,2],[3,0]]) -> [1, 2, 1]

Complexity and Choosing Between BFS and DFS

Variants and Where This Shows Up in Real Systems

That last row is a known trap: Course Schedule III isn't a graph problem at all. Reading the actual constraints before pattern-matching on the title is a habit that pays off.

Real-world topological sorting

• Build tools such as Maven, Gradle and Bazel build modules in dependency order and fail with a "cycle detected" error when two modules depend on each other.
• Package managers (npm, pip) resolve install order from dependency graphs.
• Workflow schedulers like Apache Airflow define pipelines as DAGs; the "A" in DAG is exactly the no-cycle guarantee.
• Spreadsheets recompute cells in dependency order and report circular references.
• Database migrations and service startup order components so dependencies come up first.

Mentioning one of these in an interview, briefly, shows you see the algorithm as a tool rather than a puzzle answer. For deeper system design versions, the job-scheduling problem in system design rounds relies on the same DAG ideas.

How Course Schedule Shows Up in Interviews

Course Schedule is commonly reported at Amazon, Google, Microsoft, Uber and Indian product companies like Flipkart and Swiggy, often as the graph question in an SDE-1 or SDE-2 loop. A good answer usually includes:

1. The model: "Courses are nodes, [a, b] is an edge b → a, and the answer is whether the graph is a DAG."
2. An algorithm choice with a reason: "I'll use Kahn's algorithm because it's iterative and gives the order directly if you want it."
3. Clean graph building, including courses with no edges (they start with in-degree 0 and must be counted).
4. A dry run of a cyclic case that also contains valid courses, like Example B.
5. Complexity as O(V + E) with the reason.

Follow-up questions to prepare

• "Why three colors?" The diamond and back-edge examples above.
• "What's the minimum number of semesters if you can take any number of courses per semester?" Kahn's by levels.
• "At most k courses per semester?" That's LeetCode 1494 and is much harder (bitmask DP); recognising that it's a different complexity class is the point.
• "Return the lexicographically smallest valid order." Min-heap instead of a queue.
• "Prerequisites change over time; keep answering." Incremental cycle detection; for an interview, rerunning in O(V + E) per change or checking reachability before adding each edge is a reasonable answer.

Common mistakes

• Reversed edges in Course Schedule II, producing the order backwards.
• A single visited set in DFS, which either misses cycles or reports false ones.
• Starting DFS only from node 0, missing cycles in other components.
• Forgetting isolated courses in Kahn's initial queue.
• Using Union-Find for a directed graph.
• Python recursion depth on long chains.

Course Schedule pairs well with Number of Islands (connected components in undirected grids) and with weighted problems in shortest path algorithms. If the recursive DFS still feels risky, revisit recursion for beginners, then write the three-color DFS from memory until it takes under five minutes. That's about the speed interviewers expect.

Frequently Asked Questions

Pranjal Jain

Ex-Microsoft SDE · IIT Kanpur · Founder of Prepflix. Helps engineers crack startup and product company interviews across India.