Course Schedule Problem: Topo Sort That Detects Cycles

You're given numCourses and a list of [course, prerequisite] pairs, and you're asked: can you finish all courses? Strip away the story and it's the most-asked graph question in interviews — directed cycle detection, LeetCode 207. You'll be tempted to DFS from every node and eyeball it. Don't. There's an iterative peeling algorithm that answers in O(V + E) with zero recursion risk.

The failure mode is specific: candidates build the graph backwards (edges course → prerequisite), seed the queue with only mentioned courses, and return True from inside the loop. Each mistake passes the samples and dies on hidden tests. This walkthrough shows the brute force so you can narrate it, then locks in Kahn's topological sort with the exact edge direction, queue seeding, and counting rule.

You'll get runnable Python, the four bugs that flip 1 in 2 submissions, and the Course Schedule II follow-up that interviewers ask when part I goes well.

Problem Walkthrough — Courses Are a Directed Graph

LeetCode 207: numCourses labeled 0..n-1, plus prerequisites pairs [a, b] meaning 'take b before a'. Return True iff every course can be completed. Constraints reach 2000 courses and 5000 pairs — O(V·E) brute force dies here.

Model it as a directed graph: node per course, edge b → a per pair. A valid schedule is a topological ordering — a sequence where every edge points forward. Such an ordering exists exactly when the graph has no directed cycle. Self-loop [0,0] is a cycle. Mutual pairs [1,0],[0,1] are a cycle.

Example 1: n=2, [[1,0]] → edge 0→1, order [0,1], True. Example 2: n=2, [[1,0],[0,1]] → cycle, False. The algorithm must handle disconnected components and isolated courses (no pairs at all → trivially True).

Brute Force — Why Plain DFS Explodes

The brute force runs unmemoized DFS from every course, following prerequisite chains to look for a path back to the start. Each node fans out to all its dependents, so dense graphs explore O(2^V) paths. With V = 2000 this never finishes.

Adding a visited set per DFS root helps but stays O(V·(V+E)) — up to 2000 × 7000 ≈ 1.4×10^7, borderline in Python and still wrong-shaped: a single global visited set confuses cross-path revisits with real cycles, flipping diamond DAGs to False.

The fix in both dimensions is doing each edge once: either three-color DFS or Kahn's peeling, both O(V + E). The brute force is worth 30 seconds of narration ('I'd never ship this because...') and zero lines of final code.

Optimal Approach — Kahn's In-Degree Peeling

Kahn's algorithm: compute indegree[c] = number of unmet prerequisites for each course. Queue every course with indegree 0 (no prerequisites — takable now). Repeatedly pop a course, count it as taken, and decrement the indegree of each dependent; any dependent hitting 0 joins the queue.

When the queue empties, taken == numCourses means every course was peelable → DAG → True. Otherwise the unpeeled remainder sits in or behind a directed cycle → False. Each node and edge is processed once: O(V + E) time, O(V + E) space for the adjacency list.

Trace [[1,0],[2,1],[0,2]] with n=3: indegrees [1,1,1], queue empty, taken=0 → False (3-cycle). Trace [[1,0],[2,0],[3,1],[3,2]] n=4: queue [0], pop 0 → queue [1,2], pop both → queue [3], taken=4 → True.

Kahn's Algorithm in Full Python

The code has three load-bearing lines: the edge construction (graph[src].append(dest)), the queue seeding over range(numCourses), and the final taken == numCourses verdict. Everything else is standard BFS.

The __main__ block encodes five discriminating cases: both samples, the isolated-course test (n=4 with only 3 mentioned), the self-loop, and the diamond DAG that kills single-visited-set DFS. Run all five before submitting.

from collections import defaultdict, deque
from typing import List


class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        """Kahn's BFS topo sort: O(V + E) time. True iff no directed cycle."""
        graph = defaultdict(list)
        indegree = [0] * numCourses
        for dest, src in prerequisites:
            graph[src].append(dest)
            indegree[dest] += 1
        queue: deque[int] = deque(
            i for i in range(numCourses) if indegree[i] == 0
        )
        taken = 0
        while queue:
            node = queue.popleft()
            taken += 1
            for nxt in graph[node]:
                indegree[nxt] -= 1
                if indegree[nxt] == 0:
                    queue.append(nxt)
        return taken == numCourses


if __name__ == "__main__":
    s = Solution()
    assert s.canFinish(2, [[1, 0]]) is True
    assert s.canFinish(2, [[1, 0], [0, 1]]) is False
    assert s.canFinish(4, [[1, 0], [2, 1]]) is True  # course 3 isolated
    assert s.canFinish(1, [[0, 0]]) is False  # self-loop
    assert s.canFinish(4, [[1, 0], [2, 0], [3, 1], [3, 2]]) is True
    print("all checks passed")

Self-Dependencies, Disconnected Courses and Empty Prerequisites

Zero prerequisites → True regardless of numCourses. Self-loop [[0,0]] → False. Duplicate pairs [[1,0],[1,0]] → True logically (dedupe or state the no-duplicates assumption). Disconnected graph with one cyclic component → False (leftovers fail the count).

Large input: numCourses = 2000 with no pairs means the queue starts with 2000 entries and the loop pops all — True, O(V). Chain of 2000 linear prerequisites → True with the queue holding exactly 1 node at a time. Both shapes must work; the chain shape is where recursive DFS risks stack overflow, which is why Kahn's is the pressure-proof pick.

The diamond [[1,0],[2,0],[3,1],[3,2]] must be True — it is the test that separates three-color/Kahn's (correct) from single-visited-set DFS (false cycle).

Complexity — Why O(V + E) Iterative Wins

Kahn's BFS: O(V + E) time — each node queued once, each edge relaxed once. O(V + E) space for adjacency plus indegree array. Iterative, so no recursion limit regardless of chain depth.

Three-color DFS: same O(V + E) bounds with O(V) stack in the worst case — fine for V = 2000 in most languages but a stack-overflow risk in Python on deep chains without sys.setrecursionlimit.

Naive approaches: unmemoized DFS O(2^V); per-root visited DFS O(V·(V+E)). Union-find is inapplicable (undirected tool, directed problem). Present Kahn's as the default and name three-color DFS as the alternative that also yields orderings.