loading

Course Schedule — Step-by-Step Visualization

mediumLeetCode #207GraphDFSBFSTopological Sort

There are a total of `numCourses` courses you have to take, labeled from 0 to `numCourses - 1`. You are given an array `prerequisites` where `prerequisites[i] = [ai, bi]` indicates that you must take course `bi` first if you want to take course `ai`. Return true if you can finish all courses. Otherwise, return false.

Algorithm Pattern

Cycle Detection in Directed Graph (DFS)

Key Idea

This is a classic problem of detecting a cycle in a directed graph. We can represent the courses as nodes and prerequisites as directed edges. If the graph is a Directed Acyclic Graph (DAG), we can finish all courses. We use DFS with three states for each node: 0 (unvisited), 1 (visiting/in current recursion stack), and 2 (visited/fully processed). If we encounter a node in state 1 during DFS, a cycle exists.

Step-by-Step Approach

  1. Build an adjacency list from the prerequisites.
  2. Initialize `visitStatus` array with 0s for all courses.
  3. For each course `i`:
  4. If `dfs(i)` returns `False`, return `False`.
  5. In DFS: If status is 1, cycle found (return `False`). If status is 2, already processed (return `True`).
  6. Set status to 1, recursively call DFS on all neighbors.
  7. Set status to 2, return `True`.

Common Gotchas

  • The prereq `[a, b]` means an edge `b -> a` (take `b` before `a`).
  • The graph may not be fully connected, so we must start DFS from every unvisited node.

Related Problems

← All problems