163. Course Schedule

A prerequisite [a, b] means edge b → a. You can take all courses iff the graph is a DAG — equivalent to "every course can be drained by repeatedly removing those with zero unmet prerequisites."

Approach

1. Build adjacency list and in-degree counts.
2. Enqueue every course with in-degree 0.
3. Pop one; for each neighbor, decrement its in-degree; if it hits 0, enqueue.
4. If we popped all numCourses, return True.

import java.util.*;

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<List<Integer>> graph = new ArrayList<>();
        int[] indeg = new int[numCourses];
        for (int i = 0; i < numCourses; i++) graph.add(new ArrayList<>());
        for (int[] p : prerequisites) {
            graph.get(p[1]).add(p[0]);
            indeg[p[0]]++;
        }
        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (indeg[i] == 0) q.add(i);
        }
        int taken = 0;
        while (!q.isEmpty()) {
            int u = q.poll();
            taken++;
            for (int v : graph.get(u)) {
                indeg[v]--;
                if (indeg[v] == 0) q.add(v);
            }
        }
        return taken == numCourses;
    }
}

We can take all courses iff the prerequisite graph has no cycles. The clean way to detect cycles in a directed graph during DFS is the three-colour scheme: every node is WHITE (unvisited), GRAY (on the current DFS path), or BLACK (fully explored). If DFS ever steps onto a GRAY node, we've found a back-edge — a cycle.

Why three colours, not two

A two-colour DFS (visited / unvisited) catches some cycles but not all in a directed graph. Distinguishing "in progress" (currently on the recursion stack) from "done" (all descendants explored, currently returned) is what makes back-edge detection precise:

• WHITE → GRAY: when DFS first enters the node.
• GRAY → BLACK: when DFS finishes all neighbours and returns from the node.
• Hitting a GRAY neighbour: we're trying to follow an edge to an ancestor on the current path — that's a cycle.
• Hitting a BLACK neighbour: that subtree was already explored in a previous DFS, no need to re-enter.

Steps

1. Build the adjacency list. A prerequisite [a, b] means b → a (you must finish b before a).
2. Initialise state = [WHITE] * numCourses.
3. For each course i:
   • If state[i] == WHITE, run dfs(i). If it returns False, return False.
4. Return True.

dfs(u):

• Mark state[u] = GRAY.
• For each v in graph[u]:
  • If state[v] == GRAY, return False (cycle).
  • If state[v] == WHITE, recurse — if it returns False, propagate.
• Mark state[u] = BLACK.
• Return True.

Walk-through 1: canFinish(2, [[1, 0]]) (no cycle)

Graph: 0 → 1. State: [W, W].

• dfs(0): state → [G, W]. Neighbours: [1]. state[1] == WHITE → recurse dfs(1).
  • dfs(1): state → [G, G]. No neighbours. state → [G, B]. return True.
• back in dfs(0): state → [B, B]. return True.

Outer loop tries dfs(1) but state[1] == BLACK (skip via state[i] == BLACK or dfs(i) short-circuit).

Result: True. ✓

Walk-through 2: canFinish(2, [[1, 0], [0, 1]]) (cycle)

Graph: 0 → 1, 1 → 0. State: [W, W].

• dfs(0): state → [G, W]. Neighbours: [1]. recurse dfs(1).
  • dfs(1): state → [G, G]. Neighbours: [0]. state[0] == GRAY → return False.
• back in dfs(0): returns False.

Outer call returns False. ✓

Why the outer loop guard state[i] == BLACK or dfs(i) works

Some courses may be part of disconnected components. The outer sweep ensures we run DFS from every potential start. The state[i] == BLACK short-circuit avoids re-running DFS on courses already finished. (You could also check state[i] == WHITE; both work — anything not-WHITE has been seen.)

Edge cases

• No prerequisites: every course is white, every DFS finishes immediately. Return True.
• Self-loop [a, a]: an edge from a to itself. DFS enters a (GRAY), iterates neighbours, sees a (GRAY) → cycle. Return False.
• Multiple disjoint chains: each gets its own DFS via the outer sweep.

Complexity

• Time: O(V + E) — each node is entered once and each edge inspected once.
• Space: O(V + E) for the adjacency list, plus O(V) for the state array and recursion stack.