⚠️ This visualization was AI-generated and may contain inaccuracies. Please verify against the original LeetCode problem (#207) before relying on it.

🎓 Course Schedule

An interactive visualization of DFS-based cycle detection in a directed graph. Watch how three coloring states (white/gray/black) detect cycles in prerequisite dependencies.

DFS LeetCode 207 ↗ Medium

The Problem

There are numCourses courses labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [a, b] indicates that you must take course b before course a.

Return true if you can finish all courses (i.e., there is no cycle in the prerequisite graph). Return false if there is a cycle that makes it impossible to complete all courses.

Interactive Visualization

Number of Courses

Prerequisites

Preset

Speed:

Directed Graph

White (unvisited)

Gray (visiting / on stack)

Black (done / safe)

Color State Array

Code

fun canFinish(numCourses: Int, prerequisites: Array<IntArray>): Boolean {    val graph = Array(numCourses) { mutableListOf<Int>() }    for ((a, b) in prerequisites)        graph[b].add(a)    // 0=white, 1=gray, 2=black    val color = IntArray(numCourses)    fun dfs(node: Int): Boolean {        color[node] = 1  // gray (visiting)        for (neighbor in graph[node]) {            if (color[neighbor] == 1)                return false  // cycle!            if (color[neighbor] == 0)                if (!dfs(neighbor)) return false        }        color[node] = 2  // black (done)        return true    }    for (i in 0 until numCourses)        if (color[i] == 0)            if (!dfs(i))                return false    return true}

def canFinish(numCourses, prerequisites):    graph = [[] for _ in range(numCourses)]    for a, b in prerequisites:        graph[b].append(a)    # 0=white, 1=gray, 2=black    color = [0] * numCourses    def dfs(node):        color[node] = 1  # gray (visiting)        for neighbor in graph[node]:            if color[neighbor] == 1:                return False  # cycle!            if color[neighbor] == 0:                if not dfs(neighbor):                    return False        color[node] = 2  # black (done)        return True    for i in range(numCourses):        if color[i] == 0:            if not dfs(i):                return False    return True

Status

Press Step or Play to begin.

How It Works

Key Insight

Use three-color DFS to detect cycles in a directed graph. Each node has one of three states: white (unvisited), gray (currently being explored — on the recursion stack), and black (fully processed — all descendants checked and safe). If during DFS we encounter a gray node, we have found a back edge, which means a cycle exists.

The Algorithm

Build graph: Create an adjacency list from the prerequisites. Each edge [a, b] becomes graph[b] → a (b must come before a).
Initialize colors: All nodes start as white (color = 0).
For each unvisited node: Start a DFS traversal.
Enter node: Mark it gray (color = 1) — it is now on the recursion stack.
Explore neighbors: For each neighbor:
- If gray: cycle detected! Return False.
- If white: recursively DFS into it.
- If black: skip (already safe).
Finish node: Mark it black (color = 2) — all descendants are safe.
Result: If all nodes are processed without finding a cycle, return True.

Complexity

Time O(V + E)

Space O(V + E)

We visit each node and each edge at most once during DFS, giving O(V + E) time. The adjacency list requires O(V + E) space, and the recursion stack can be at most O(V) deep.