6.2 Course Schedule

6.2.1 Problem Metadata

6.2.2 Description

Given numCourses labeled 0..n-1 and prerequisite pairs [a, b] meaning b -> a, determine if it’s possible to finish all courses (i.e., the graph is acyclic).

6.2.3 Examples

Example 1: All Courses Finishable

Input: numCourses = 2, prerequisites = [[1,0]]
(Course 0 must be completed before Course 1)
Output: true
Explanation: Course order: [0, 1]

Example 2: Cycle Exists

Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Explanation: Course 1 requires Course 0, and Course 0 requires Course 1 — impossible!

Example 3: No Prerequisites

Input: numCourses = 3, prerequisites = []
Output: true
Explanation: No dependencies, can finish all courses in any order

6.2.4 Constraints

  • 1 ≤ numCourses ≤ 2000
  • 0 ≤ prerequisites.length ≤ 5000
  • Each prerequisite pair [a, b] satisfies 0 ≤ a, b < numCourses
  • All prerequisite pairs are unique

6.2.5 Solution - Kahn’s Algorithm

6.2.5.1 Walkthrough

Kahn’s algorithm performs BFS topological sorting to detect cycles:

  1. Build an adjacency list graph[b] -> list of a and indegree array for each course.
  2. Push all zero-indegree courses into a queue — these have no unmet prerequisites.
  3. Pop from queue, increment visited, and decrement indegree of neighbors; when a neighbor hits zero, enqueue it.
  4. If we process all courses (visited == numCourses), the graph is acyclic and all courses can be finished; otherwise a cycle exists.

This works because nodes in a cycle never reach indegree zero, preventing full traversal.

6.2.5.2 Analysis

  • Time Complexity: O(V + E)
  • Space Complexity: O(V + E) for adjacency list, indegrees, and queue

6.2.5.3 Code - BFS

public boolean canFinish(int numCourses, int[][] prerequisites) {
    List<List<Integer>> graph = new ArrayList<>();
    int[] indegree = new int[numCourses];

    for (int i = 0; i < numCourses; i++) {
        graph.add(new ArrayList<>());
    }

    // Build graph: prereq[1] -> prereq[0]
    for (int[] edge : prerequisites) {
        graph.get(edge[1]).add(edge[0]);
        indegree[edge[0]]++;
    }

    Queue<Integer> queue = new LinkedList<>();
    for (int i = 0; i < numCourses; i++) {
        if (indegree[i] == 0) {
            queue.offer(i);
        }
    }

    int visited = 0;
    while (!queue.isEmpty()) {
        int course = queue.poll();
        visited++;
        
        for (int next : graph.get(course)) {
            if (--indegree[next] == 0) {
                queue.offer(next);
            }
        }
    }
    return visited == numCourses;
}

6.2.6 Solution - DFS with Color Marking

6.2.6.1 Walkthrough

Use DFS with a three-state color marking system to detect cycles:

State Definitions: - White (0): Node not yet visited - Gray (1): Node is currently in the recursion stack (part of the current DFS path) - Black (2): Node is fully processed (all descendants explored)

Algorithm:

  1. Create a state array state[numCourses] initialized to 0 (white).
  2. Build the adjacency list: for each prerequisite [a, b], add edge b → a (course b must be done before a).
  3. For each unvisited node (state = 0), start a DFS traversal.
  4. In DFS:
    • If we encounter a gray node, a cycle exists (we’re revisiting a node in the current path) → return false.
    • If we encounter a black node, it’s already safe → return true.
    • Mark the current node as gray, recursively visit all neighbors, then mark as black.
  5. If all nodes can be traversed without encountering a gray node, no cycle exists → return true.

Why This Works: A cycle exists if and only if we revisit a node while it’s still on the current recursion path (gray state). Once a node finishes processing (black state), we know that subtree is acyclic.

6.2.6.2 Analysis

  • Time Complexity: O(V + E) — each node is visited once and each edge is traversed once
  • Space Complexity: O(V + E) — adjacency list uses O(V + E) space; recursion stack uses O(V) in worst case

6.2.6.3 Code - DFS with Color Marking

public boolean canFinish(int numCourses, int[][] prerequisites) {
    List<List<Integer>> graph = new ArrayList<>();
    int[] state = new int[numCourses]; // 0: white, 1: gray, 2: black

    for (int i = 0; i < numCourses; i++) {
        graph.add(new ArrayList<>());
    }

    // Build graph: prereq[1] -> prereq[0]
    for (int[] prereq : prerequisites) {
        graph.get(prereq[1]).add(prereq[0]);
    }

    // Check each unvisited node
    for (int i = 0; i < numCourses; i++) {
        if (state[i] == 0 && !dfs(graph, i, state)) {
            return false;
        }
    }

    return true;
}

private boolean dfs(List<List<Integer>> graph, int node, int[] state) {
    if (state[node] == 1) {
        return false; // Gray node = cycle detected
    }
    if (state[node] == 2) {
        return true;  // Black node = already safe
    }

    state[node] = 1; // Mark as gray (in current path)

    for (int neighbor : graph.get(node)) {
        if (!dfs(graph, neighbor, state)) {
            return false;
        }
    }

    state[node] = 2; // Mark as black (finished)
    return true;
}

6.2.7 Solution - DFS with Recursion Stack

6.2.7.1 Walkthrough

Use DFS with an explicit recursion stack (a Set) to track nodes currently in the current recursion path. This is conceptually equivalent to the color marking approach but uses a Set instead of a state array.

Algorithm:

  1. Build the adjacency list with edges b → a for each prerequisite [a, b].
  2. Create a visited Set to track fully processed nodes and a recursionStack Set to track nodes currently in the recursion path.
  3. For each unvisited node, start a DFS traversal.
  4. In DFS:
    • If the node is in recursionStack, a cycle exists (we’re revisiting a node in the current path) → return false.
    • If the node is in visited, it’s already safe → return true.
    • Add the node to recursionStack, recursively visit all neighbors, then remove from recursionStack and add to visited.
  5. If all nodes complete without cycles, return true.

Key Difference from Color Marking: Instead of using state values (0/1/2), we maintain two Sets: - recursionStack: Nodes currently on the recursion path (equivalent to “gray”) - visited: Nodes fully processed (equivalent to “black”)

6.2.7.2 Analysis

  • Time Complexity: O(V + E)
  • Space Complexity: O(V + E) — adjacency list plus two Sets, recursion stack uses O(V)

6.2.7.3 Code - DFS with Recursion Stack

public boolean canFinish(int numCourses, int[][] prerequisites) {
    List<List<Integer>> graph = new ArrayList<>();
    Set<Integer> visited = new HashSet<>();
    Set<Integer> recursionStack = new HashSet<>();

    for (int i = 0; i < numCourses; i++) {
        graph.add(new ArrayList<>());
    }

    // Build graph: prereq[1] -> prereq[0]
    for (int[] prereq : prerequisites) {
        graph.get(prereq[1]).add(prereq[0]);
    }

    // Check each unvisited node
    for (int i = 0; i < numCourses; i++) {
        if (!visited.contains(i) && !dfs(graph, i, visited, recursionStack)) {
            return false;
        }
    }

    return true;
}

private boolean dfs(List<List<Integer>> graph, int node, Set<Integer> visited, Set<Integer> recursionStack) {
    if (recursionStack.contains(node)) {
        return false; // Cycle detected: node is in current path
    }
    if (visited.contains(node)) {
        return true;  // Node already safe
    }

    recursionStack.add(node); // Add to current path

    for (int neighbor : graph.get(node)) {
        if (!dfs(graph, neighbor, visited, recursionStack)) {
            return false;
        }
    }

    recursionStack.remove(node); // Remove from current path
    visited.add(node);           // Mark as fully processed
    return true;
}

6.2.8 Solution - DFS with Post-order Visiting

6.2.8.1 Walkthrough

Use DFS with post-order visiting: mark a node as “safe” only after processing all its descendants. This approach uses a visiting Set to detect cycles and a visited Set to mark completed nodes.

Algorithm:

  1. Build the adjacency list with edges b → a.
  2. Create a visiting Set to track nodes currently being processed and a visited Set for fully processed nodes.
  3. For each unvisited node, start a DFS traversal.
  4. In DFS:
    • If the node is in visiting, a cycle exists → return false.
    • If the node is in visited, it’s already safe → return true.
    • Add the node to visiting, recursively visit all neighbors, then remove from visiting and add to visited.
  5. Post-order means nodes are marked “visited” only after all their descendants are safely processed.

When This is Useful: This approach is conceptually similar to the recursion stack method but emphasizes the post-order traversal pattern, which is useful when you need to process nodes after their dependencies are resolved.

6.2.8.2 Analysis

  • Time Complexity: O(V + E)
  • Space Complexity: O(V + E) — adjacency list plus two Sets, recursion stack uses O(V)

6.2.8.3 Code - DFS with Post-order

public boolean canFinish(int numCourses, int[][] prerequisites) {
    List<List<Integer>> graph = new ArrayList<>();
    Set<Integer> visiting = new HashSet<>();
    Set<Integer> visited = new HashSet<>();

    for (int i = 0; i < numCourses; i++) {
        graph.add(new ArrayList<>());
    }

    // Build graph: prereq[1] -> prereq[0]
    for (int[] prereq : prerequisites) {
        graph.get(prereq[1]).add(prereq[0]);
    }

    // Check each unvisited node
    for (int i = 0; i < numCourses; i++) {
        if (!visited.contains(i) && !dfs(graph, i, visiting, visited)) {
            return false;
        }
    }

    return true;
}

private boolean dfs(List<List<Integer>> graph, int node, Set<Integer> visiting, Set<Integer> visited) {
    if (visiting.contains(node)) {
        return false; // Cycle detected during traversal
    }
    if (visited.contains(node)) {
        return true;  // Already processed in post-order
    }

    visiting.add(node); // Mark as currently visiting

    for (int neighbor : graph.get(node)) {
        if (!dfs(graph, neighbor, visiting, visited)) {
            return false;
        }
    }

    visiting.remove(node);  // Done with current path
    visited.add(node);      // Post-order: mark as visited after processing descendants
    return true;
}

Comparison of All Three DFS Approaches:

Approach State Tracking Cycle Detection Space
Color Marking int[] state (0/1/2) Check for gray (state=1) O(V) array
Recursion Stack Two Sets Check recursionStack Set O(V) Sets
Post-order Two Sets Check visiting Set O(V) Sets

All three are equivalent in terms of time/space complexity and correctness. Choose based on code clarity preference.