Course Schedule

Do a DFS from every course, coloring each node unvisited -> visiting -> done. If DFS ever reaches a node that is currently visiting (an ancestor in the current recursion path), that is a back edge, meaning a cycle.

class Solution:
    def canFinish(self, numCourses: int, prerequisites: list[list[int]]) -> bool:
        graph = [[] for _ in range(numCourses)]
        for a, b in prerequisites:
            graph[a].append(b)

        UNVISITED, VISITING, DONE = 0, 1, 2
        state = [UNVISITED] * numCourses

        def dfs(u):
            if state[u] == VISITING:
                return False  # back edge -> cycle
            if state[u] == DONE:
                return True   # already confirmed safe

            state[u] = VISITING
            for v in graph[u]:
                if not dfs(v):
                    return False
            state[u] = DONE
            return True

        return all(dfs(u) for u in range(numCourses))

Tracing on the example, starting dfs(0) through dfs(3) in order:

1. dfs(0): mark 0 VISITING. No dependencies. Mark 0 DONE. Returns True.
2. dfs(1): mark 1 VISITING. Recurse into dependency 0 (DONE, returns True immediately). Recurse into dependency 3.
3. dfs(3): mark 3 VISITING. Recurse into dependency 2.
4. dfs(2): mark 2 VISITING. Recurse into dependency 1 — but 1 is currently VISITING (it’s the caller three frames up!). This is a back edge: dfs(1) returns False immediately, which propagates back through dfs(2), dfs(3), and dfs(1), and the overall function returns False.

Why it’s correct: a node colored VISITING is exactly a node currently on the DFS call stack — an ancestor of the current node in the DFS tree. Reaching it again means there is a path from it back to itself, i.e. a cycle. Complexity: each node is fully processed (colored DONE) once and each edge is traversed once → O(V + E) time; the color array, adjacency list, and recursion stack are all O(V + E) space.

Repeatedly peel off courses that have no remaining unfinished prerequisites (in-degree 0 in the “depends on” sense) — track it as out-degree in a graph pointing prerequisite → dependent instead. If every course eventually gets peeled off, there is no cycle. This avoids recursion entirely, which matters for very deep dependency chains.

from collections import deque

class Solution:
    def canFinish(self, numCourses: int, prerequisites: list[list[int]]) -> bool:
        graph = [[] for _ in range(numCourses)]
        indegree = [0] * numCourses
        for a, b in prerequisites:
            graph[b].append(a)  # b unlocks a
            indegree[a] += 1

        queue = deque(u for u in range(numCourses) if indegree[u] == 0)
        finished = 0

        while queue:
            u = queue.popleft()
            finished += 1
            for v in graph[u]:
                indegree[v] -= 1
                if indegree[v] == 0:
                    queue.append(v)

        return finished == numCourses

Watch it on the first statement example — n = 2, prerequisites = [[1,0]]. Course 0 is ready from the start; finishing it redeems the one prerequisite holding course 1 back, and the readiness ripples through the queue:

Now the running example from the top of the page — n = 4, prerequisites = [[1,0],[2,1],[3,2],[1,3]], where course 1 must wait for both 0 and 3. Watch the queue run dry — and what that emptiness proves about the courses left behind:

Why it’s correct: a course can only be queued once every prerequisite has already been processed. If a cycle exists, every course in it perpetually has at least one un-processed prerequisite (another course in the same cycle), so it can never reach in-degree 0 and never gets counted — exactly what finished == numCourses checks. Complexity: each node is enqueued once and each edge decrements exactly one in-degree counter → O(V + E) time, O(V + E) space for the graph and in-degree array. Same asymptotic cost as the DFS version, but iterative, avoiding any recursion-depth concerns on graphs with long dependency chains.