Course Schedule

Problem Statement

You’re a student planner with numCourses and prerequisites (pairs [a,b] meaning b before a). Can you finish all courses without a cycle? This medium-level graph problem is a dependency dance—use DFS or BFS to detect loops!

Example

Input: numCourses = 2, prerequisites = [[1,0]]

Output: true (0→1 is acyclic)

Input: numCourses = 2, prerequisites = [[1,0],[0,1]]

Output: false (Cycle: 0↔1)

Input: numCourses = 4, prerequisites = [[1,0],[2,1],[3,2]]

Output: true (0→1→2→3)

Code

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List> graph = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) graph.add(new ArrayList<>());
        for (int[] pre : prerequisites) graph.get(pre[1]).add(pre[0]);
        int[] visited = new int[numCourses]; // 0=unvisited, 1=visiting, 2=visited
        for (int i = 0; i < numCourses; i++) {
            if (visited[i] == 0 && !dfs(graph, i, visited)) return false;
        }
        return true;
    }
    private boolean dfs(List> graph, int node, int[] visited) {
        visited[node] = 1;
        for (int next : graph.get(node)) {
            if (visited[next] == 1) return false; // Cycle
            if (visited[next] == 0 && !dfs(graph, next, visited)) return false;
        }
        visited[node] = 2;
        return true;
    }
}
            

from collections import defaultdict
class Solution:
    def canFinish(self, numCourses, prerequisites):
        graph = defaultdict(list)
        for a, b in prerequisites:
            graph[b].append(a)
        visited = [0] * numCourses  # 0=unvisited, 1=visiting, 2=visited
        def dfs(node):
            if visited[node] == 1:
                return False
            if visited[node] == 2:
                return True
            visited[node] = 1
            for next_node in graph[node]:
                if not dfs(next_node):
                    return False
            visited[node] = 2
            return True
        for i in range(numCourses):
            if visited[i] == 0 and not dfs(i):
                return False
        return True
            

function canFinish(numCourses, prerequisites) {
    let graph = Array(numCourses).fill().map(() => []);
    for (let [a, b] of prerequisites) graph[b].push(a);
    let visited = new Array(numCourses).fill(0); // 0=unvisited, 1=visiting, 2=visited
    function dfs(node) {
        if (visited[node] === 1) return false;
        if (visited[node] === 2) return true;
        visited[node] = 1;
        for (let next of graph[node]) {
            if (!dfs(next)) return false;
        }
        visited[node] = 2;
        return true;
    }
    for (let i = 0; i < numCourses; i++) {
        if (visited[i] === 0 && !dfs(i)) return false;
    }
    return true;
}
            

Explanation

• DFS Insight: Detect cycles in directed graph; cycle means impossible schedule.
• Flow: Build adjacency list, DFS with three states to catch back edges.
• Example Walkthrough: [[1,0],[0,1]] → 0→1→0 (cycle detected) → false.
• BFS Alt: Kahn’s algorithm with in-degree—remove nodes with no prereqs.
• Optimization: Early exit on cycle saves time.

Note