Course Schedule: cycle detection (can all courses be finished?)

• Course Schedule reduces to detecting a cycle in a directed graph.
• Adjacency list maps each prerequisite to the courses that depend on it.
• DFS three-color marks nodes white (unvisited), gray (on current path), black (fully explored); a gray neighbor means a back edge and thus a cycle.
• Kahn's algorithm processes zero-in-degree nodes; if the processed count falls short of total, a cycle blocks the remaining nodes.
• Time is O(V + E) for both approaches; space is O(V + E) for the graph.

What is the Course Schedule problem?

Given a number of courses and a list of prerequisite pairs [course, prerequisite], determine whether it is possible to finish all courses. This is equivalent to checking whether the prerequisite directed graph is acyclic. If there is a cycle, some courses can never be completed because they depend on each other in a loop.

package com.bank.service;

import java.util.*;

public class OnboardingValidator {
    // Kahn's algorithm: can all steps be completed?
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<List<Integer>> adj = new ArrayList<>();
        int[] inDegree = new int[numCourses];
        for (int i = 0; i < numCourses; i++) adj.add(new ArrayList<>());

        for (int[] pre : prerequisites) {
            adj.get(pre[1]).add(pre[0]);
            inDegree[pre[0]]++;
        }

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

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

Why does this reduce to cycle detection?

A directed graph is acyclic if and only if it has a valid topological ordering. If a cycle exists, no topological ordering exists because the cycle's nodes all depend on each other. Detecting a cycle is equivalent to checking whether a topological sort is possible.

No cycle (finishable):       Cycle (not finishable):
  0 → 1 → 2                   0 → 1
                                ↑   ↓
                                3 ← 2

How does the DFS three-color approach work?

Color each node white (unvisited), gray (on the current recursion path), or black (fully explored). When entering a node, mark it gray. If you encounter a neighbor that is already gray, you have found a back edge and thus a cycle. When leaving a node (all descendants explored), mark it black.

public boolean canFinishDFS(int numCourses, int[][] prerequisites) {
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < numCourses; i++) adj.add(new ArrayList<>());
    for (int[] pre : prerequisites) adj.get(pre[1]).add(pre[0]);

    int[] color = new int[numCourses];  // 0=white, 1=gray, 2=black
    for (int i = 0; i < numCourses; i++) {
        if (color[i] == 0 && hasCycle(i, adj, color)) return false;
    }
    return true;
}

private boolean hasCycle(int node, List<List<Integer>> adj, int[] color) {
    color[node] = 1;  // gray: on current path
    for (int next : adj.get(node)) {
        if (color[next] == 1) return true;   // back edge → cycle
        if (color[next] == 0 && hasCycle(next, adj, color)) return true;
    }
    color[node] = 2;  // black: fully explored
    return false;
}

Why is three-color marking necessary for DFS?

A plain boolean visited flag cannot distinguish between a back edge (which signals a cycle) and a cross or forward edge to an already-finished node (which does not). The gray state means "I am currently on this path," and the black state means "I already finished exploring this node and found no cycle from it." Only a gray neighbor indicates a cycle.

// WRONG: plain visited flag
if (visited[next]) return true;  // may be a cross edge, not a cycle!

// CORRECT: three-color check
if (color[next] == 1) return true;  // gray = back edge = cycle
if (color[next] == 2) continue;     // black = already done, no cycle

How does Kahn's algorithm detect cycles?

Kahn's algorithm processes nodes in topological order by repeatedly removing nodes with zero in-degree. If some nodes can never reach zero in-degree (because they are in a cycle), they are never processed. The cycle is detected implicitly: if the processed count is less than the total number of nodes, a cycle remains.

How do the two approaches compare?

| Aspect | DFS Three-Color | Kahn's Algorithm |
|--------|----------------|------------------|
| Detection method | Explicit back edge | Implicit leftover count |
| Cycle identification | Can find the exact cycle | Only knows a cycle exists |
| Produces topo order | Yes (reverse finish order) | Yes (processing order) |
| Implementation | Recursive | Iterative (queue) |
| Stack overflow risk | Yes on deep graphs | No |

What are edge cases?

• Zero courses: return true (nothing to do).
• No prerequisites: all courses have in-degree 0, all are finishable.
• Self-loop [0, 0]: course 0 requires itself, which is a cycle.
• Disconnected components: each component must be independently acyclic.

// Edge case: self-loop
// prerequisites = [[0, 0]]
// In-degree of 0 is 1, it never reaches 0 → processed count = 0
// 0 < 1 → return false (cycle detected)

What are common mistakes?

The first mistake is using a plain visited boolean instead of three colors in DFS. The second mistake is building edges in the wrong direction, which inverts the prerequisite relationship. The third mistake is forgetting disconnected components and only starting DFS from node 0.

// WRONG: edges in wrong direction
adj.get(pre[0]).add(pre[1]);  // inverted!

// CORRECT: edge from prerequisite to dependent
adj.get(pre[1]).add(pre[0]);  // prereq → course

What should a senior engineer know?

At the National Bank of India, a customer-onboarding workflow had steps with prerequisite dependencies. Rajesh validated the workflow with Kahn's algorithm. When the processed count fell short, he knew a misconfiguration had introduced a circular dependency, so the validator rejected the workflow instead of letting it loop forever. The three-color DFS variant was used for debugging to identify the exact cycle and report it to the configuration team.