Course Schedule — Topological Sort With DFS

Course Schedule is the canonical interview problem for directed graph cycle detection. The variant that asks you to return a valid ordering is a small extension of the same algorithm. Together they are some of the highest-frequency graph problems in technical interviews.

The Problem

There are numCourses courses labeled 0 to numCourses - 1. You are given a list of prerequisites where prerequisites[i] = [a, b] means you must take course b before course a. Return True if you can finish all courses, otherwise False.

Example:

Input:  numCourses = 2, prerequisites = [[1, 0]]
Output: True

Input:  numCourses = 2, prerequisites = [[1, 0], [0, 1]]
Output: False

This is “is the directed graph a DAG?” If the graph has any cycle, the answer is False; otherwise a valid order exists.

Intuition

Model courses as nodes and edges as prerequisite-to-course. Run DFS with three-color marking:

• 0 = unvisited
• 1 = currently on the DFS stack (gray)
• 2 = fully processed (black)

If DFS reaches a gray node, there is a back edge, which means a cycle. The equivalent BFS approach (Kahn’s algorithm) repeatedly removes zero-in-degree nodes and counts how many you can remove; if you can remove all of them, the graph is acyclic. Kahn extends naturally to returning an order — the removal sequence is a valid order.

Explanation with Example

Take numCourses = 4, prerequisites = [[1, 0], [2, 1], [3, 2]].

Adjacency list (edges from prereq to course):

0 -> [1]
1 -> [2]
2 -> [3]
3 -> []

DFS starting from 0 marks 0 gray, 1 gray, 2 gray, 3 gray, then unwinds them all to black. No gray-on-gray collision, so return True.

For the cyclic case [[1, 0], [0, 1]], DFS from 0 visits 1, which tries to visit 0 again while state[0] == 1. Return False.

acyclic chain 0->1->2->3 (DAG, returns True):

[0]==>[1]==>[2]==>[3]
state sequence:
  0:white -> gray -> ... -> black
  after recursion settles, all become black

cyclic case 0->1, 1->0 (returns False):

[0] ==> [1]
 ^------+      DFS from 0 marks 0 gray,
               then visits 1 (gray),
               then tries to visit 0 -> still gray!
               back edge -> CYCLE

Code

def can_finish(num_courses, prerequisites):
    graph = [[] for _ in range(num_courses)]
    for a, b in prerequisites:
        graph[b].append(a)

    state = [0] * num_courses

    def dfs(node):
        if state[node] == 1:
            return False
        if state[node] == 2:
            return True
        state[node] = 1
        for nxt in graph[node]:
            if not dfs(nxt):
                return False
        state[node] = 2
        return True

    for course in range(num_courses):
        if not dfs(course):
            return False
    return True


from collections import deque

def can_finish_kahn(num_courses, prerequisites):
    graph = [[] for _ in range(num_courses)]
    indeg = [0] * num_courses
    for a, b in prerequisites:
        graph[b].append(a)
        indeg[a] += 1

    queue = deque(c for c in range(num_courses) if indeg[c] == 0)
    taken = 0
    while queue:
        node = queue.popleft()
        taken += 1
        for nxt in graph[node]:
            indeg[nxt] -= 1
            if indeg[nxt] == 0:
                queue.append(nxt)
    return taken == num_courses

public boolean canFinish(int numCourses, int[][] prerequisites) {
    List<List<Integer>> graph = new ArrayList<>();
    for (int i = 0; i < numCourses; i++) graph.add(new ArrayList<>());
    int[] indeg = new int[numCourses];
    for (int[] p : prerequisites) {
        graph.get(p[1]).add(p[0]);
        indeg[p[0]]++;
    }
    Deque<Integer> q = new ArrayDeque<>();
    for (int i = 0; i < numCourses; i++) if (indeg[i] == 0) q.offer(i);
    int taken = 0;
    while (!q.isEmpty()) {
        int node = q.poll();
        taken++;
        for (int nxt : graph.get(node)) {
            if (--indeg[nxt] == 0) q.offer(nxt);
        }
    }
    return taken == numCourses;
}

bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
    vector<vector<int>> graph(numCourses);
    vector<int> indeg(numCourses, 0);
    for (auto& p : prerequisites) {
        graph[p[1]].push_back(p[0]);
        indeg[p[0]]++;
    }
    queue<int> q;
    for (int i = 0; i < numCourses; i++) if (indeg[i] == 0) q.push(i);
    int taken = 0;
    while (!q.empty()) {
        int node = q.front(); q.pop();
        taken++;
        for (int nxt : graph[node]) {
            if (--indeg[nxt] == 0) q.push(nxt);
        }
    }
    return taken == numCourses;
}

Edge Cases

• Empty prerequisites: every ordering works; return True.
• Self-prerequisite, such as [1, 1]: this is a self-loop and a cycle; return False.
• Disconnected components: the outer loop covers every starting node, so disconnected subgraphs are handled.
• Duplicate prerequisite entries: the algorithm is robust because revisited black nodes return early.
• Large numCourses with sparse prereqs: O(V + E) handles it.
• Recursion depth: Python defaults to 1000; for very deep chains, either raise the limit or use the Kahn BFS version.

Complexity Analysis

• Time: O(V + E) where V = numCourses and E = len(prerequisites). Each node and edge is processed a constant number of times.
• Space: O(V + E) for the adjacency list and O(V) for the state array. Recursion stack is O(V) in the worst case.

If you want to ground the V plus E intuition more carefully, see /blog/big-o-notation-explained.

How to Explain It in an Interview

Use this script:

1. Translate the problem into graph language: nodes are courses, edges are prerequisite-to-course.
2. State the goal: detect a cycle in the directed graph.
3. Choose DFS three-color marking. Explain the three states and why gray-on-gray is the signature of a back edge.
4. Mention Kahn as the BFS alternative and note that it extends naturally to producing an ordering.
5. State complexity as O(V + E) for both.
6. Trace a small cyclic example to prove the cycle detection works.

A common follow-up: “Now return the order.” Switch to Kahn and emit nodes as they leave the queue.

Related Problems

• Course Schedule II: return a valid order, not just feasibility.
• Alien Dictionary: build the graph from word ordering, then topological sort.
• Minimum Height Trees: BFS peeling of leaves, conceptually related.
• Find Eventual Safe States: cycle detection variant.
• For more traversal patterns see /blog/graphs-bfs-and-dfs.

Wrap up

Course Schedule is the cleanest interview check for whether you can build a graph from input, choose between DFS and BFS thoughtfully, and reason about cycles. Memorize the three-color DFS template and the Kahn BFS template, and know which extends to which follow-up.