LeetCode: Course Schedule

2026-03-14

Build a prerequisite graph and use DFS cycle detection to check whether every course can be completed.

LeetCode: Course Schedule

Summary

Return true if you can finish all courses. Otherwise, return false.

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] means you must take course bi before course ai.

Approach

This is a graph cycle-detection problem.

We build a directed graph where each course points to its prerequisites. Then we run DFS and check whether we revisit a node that is already on the current DFS path.

If that happens, there is a cycle, so it is impossible to finish all courses.

Function

Initialization:

  • graph: adjacency list of prerequisites. The key is a course, and the value is the list of prerequisite courses.
  • done: nodes that have already been checked and confirmed to have no cycle.
  • visiting: nodes currently on the DFS path.

DFS:

Argument:

  • node

Logic:

  1. If node is in done, return False because this path is already known to be acyclic.
  2. If node is in visiting, return True because we found a cycle.
  3. Add node to visiting.
  4. For each prerequisite v in graph[node], run dfs(v).
  5. If any recursive call returns True, propagate True.
  6. Remove node from visiting.
  7. Add node to done.
  8. Return False.

Run this DFS for every course.

Complexity

Time complexity: O(V + E). Each node is fully processed once, and each edge is traversed once.

Space complexity: O(V + E). The graph takes O(V + E), and the done set, visiting set, and DFS call stack take O(V).