Course Schedule

MediumGraphsDFSBFSGraphTopological Sort

Problem

You are given a number of courses and a list of prerequisite pairs, where each pair says one course must be completed before another. Determine whether it is possible to finish every course given these constraints.

Example. If course 1 requires course 0, you can finish both by taking 0 then 1. But if course 0 also required course 1 in return, neither could ever be taken first, so finishing all courses is impossible.

Key idea

Model each course as a node and each prerequisite pair as a directed edge from the required course to the dependent one. Finishing every course is then equivalent to this directed graph having no cycle: if a group of courses forms a cycle, each depends, directly or indirectly, on another in the same group, so none can legally be first. Detecting a cycle means running a depth-first search from each unvisited node while tracking two states (currently on the active path, versus fully finished) and flagging a cycle the moment the search reaches a node still on the active path. A finished node can safely be revisited through a different path, since a directed acyclic graph can have multiple routes to one node without that being a cycle. Kahn's algorithm is an equally valid alternative: repeatedly take courses with no remaining prerequisites, and if courses are left over once no more can be taken, a cycle exists among them.

Solution

function canFinish(numCourses: number, prerequisites: number[][]): boolean {
  const graph: number[][] = Array.from({ length: numCourses }, () => []);
  for (const [course, prereq] of prerequisites) {
    graph[prereq].push(course);
  }

  const UNVISITED = 0;
  const VISITING = 1;
  const FINISHED = 2;
  const state = new Array<number>(numCourses).fill(UNVISITED);

  function hasCycle(course: number): boolean {
    if (state[course] === VISITING) {
      return true; // reached a node still on the active path: cycle
    }
    if (state[course] === FINISHED) {
      return false; // already fully explored with no cycle through it
    }

    state[course] = VISITING; // mark on the active path before exploring neighbors
    for (const next of graph[course]) {
      if (hasCycle(next)) {
        return true;
      }
    }
    state[course] = FINISHED;

    return false;
  }

  for (let course = 0; course < numCourses; course++) {
    if (hasCycle(course)) {
      return false;
    }
  }

  return true;
}

Complexity

  • Time: O(V + E). Building the adjacency list and visiting every node and edge once.
  • Space: O(V + E). For the adjacency list, the per-node state tracking, and the recursion stack.

Watch out for

  • Distinguish "on the current path" from "already fully processed," since only the former signals a cycle.
  • Every unvisited node needs its own search, since the graph may consist of several disconnected pieces.
  • A course that lists itself as its own prerequisite is a one-node cycle.

Pattern

This is cycle detection in a directed graph, the check a topological sort must pass before an ordering can exist; it is reused directly in Course Schedule II.

Related questions