Course4all
Join us on telegram
Home/dsa/Graphs/Course Schedule

Course Schedule

Master this topic with zero to advance depth.

Course Schedule

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [a_i, b_i] indicates that you must take course b_i first if you want to take course a_i.

Return true if you can finish all courses. Otherwise, return false.

Visual Representation

Courses: 2, Prerequisites: [[1, 0]] Graph: 0 -> 1 Cycle? No. Result: true Prerequisites: [[1, 0], [0, 1]] Graph: 0 <-> 1 (Cycle!) Cycle? Yes. Result: false
Medium

Examples

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

To take course 1 you should have finished course 0. So it is possible.

Approach 1

Level II: Intermediate (DFS - Cycle Detection)

Intuition

A graph is a Directed Acyclic Graph (DAG) if there are no Back Edges during DFS. We use three states for each node: 0 (unvisited), 1 (visiting/in current path), and 2 (visited). If we encounter a node with state 1, a cycle exists.

Thought Process

  1. Build an adjacency list.
  2. For each course, if not visited, launch DFS.
  3. In DFS:
    • Mark node as 1 (visiting).
    • Traverse neighbors. If a neighbor is in state 1, return false (cycle).
    • Mark node as 2 (fully processed).
  4. If no cycle is found for any node, return true.

Pattern: DFS Cycle Detection

⏱ O(V + E) - Standard DFS traversal.💾 O(V + E) - Adjacency list + recursion stack.

Detailed Dry Run

pre=[[1,0],[0,1]]

NodeStateNeighborsResult
01[1]Launch DFS(1)
11[0]0 is state 1! CYCLE!
Return--false
java
import java.util.*;

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

        int[] visited = new int[numCourses]; // 0: unvisited, 1: visiting, 2: visited
        for (int i = 0; i < numCourses; i++) {
            if (hasCycle(i, adj, visited)) return false;
        }
        return true;
    }

    private boolean hasCycle(int u, List<Integer>[] adj, int[] visited) {
        if (visited[u] == 1) return true;
        if (visited[u] == 2) return false;

        visited[u] = 1;
        for (int v : adj[u]) {
            if (hasCycle(v, adj, visited)) return true;
        }
        visited[u] = 2;
        return false;
    }
}
Approach 2

Level III: Optimal (Kahn's Algorithm - BFS)

Intuition

Kahn's algorithm uses In-Degrees to peel off nodes with no dependencies. This is the gold standard for Topological Sort as it's iterative and avoids recursion stack issues.

Thought Process

  1. Calculate the in-degree of each course (number of prerequisites).
  2. Add all courses with in-degree == 0 to a queue.
  3. While the queue is not empty:
    • Pop a course, increment completed count.
    • For each course that depends on it, decrement its in-degree.
    • If in-degree becomes 0, add to queue.
  4. If completed == numCourses, return true.

Pattern: Topological Sort

⏱ O(V + E) - Each node and edge is processed once.💾 O(V + E) - For the adjacency list and in-degree array.

Detailed Dry Run

num=2, pre=[[1,0]]

PopQueueIn-DegreesCount
-[0][0:0, 1:1]0
0[1][1:0]1
1[]-2
Result: 2 == 2 (True)
java
import java.util.*;

public class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int[] indegree = new int[numCourses];
        List<Integer>[] adj = new List[numCourses];
        for (int i = 0; i < numCourses; i++) adj[i] = new ArrayList<>();
        
        for (int[] p : prerequisites) {
            adj[p[1]].add(p[0]);
            indegree[p[0]]++;
        }

        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) if (indegree[i] == 0) q.add(i);

        int count = 0;
        while (!q.isEmpty()) {
            int curr = q.poll();
            count++;
            for (int neighbor : adj[curr]) {
                if (--indegree[neighbor] == 0) q.add(neighbor);
            }
        }
        return count == numCourses;
    }
}
← Previous QuestionHamiltonian Path
Next Question →Number of Islands