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

Course Schedule II

Master this topic with zero to advance depth.

Course Schedule II

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 the ordering of courses you should take to finish all courses. If there are many valid answers, return any of them. If it is impossible to finish all courses, return an empty array.

Visual Representation

Prerequisites: [[1, 0], [2, 0], [3, 1], [3, 2]] Graph: 0 -> 1 -> 3 0 -> 2 -> 3 Possible Order: [0, 1, 2, 3] or [0, 2, 1, 3]
Medium

Examples

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

To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0.

Approach 1

Level II: Intermediate (DFS - Post-order)

Intuition

In a DAG, if we perform DFS and record nodes in Post-order (after visiting all neighbors), and then reverse that list, we get a topological sort. We must also check for cycles using the recursion stack.

Thought Process

  1. Build adjacency list.
  2. Use a visited set to track globally visited nodes and a path (recursion stack) set for cycle detection.
  3. In DFS(u):
    • If u in path, return False (cycle found).
    • If u in visited, return True (already processed).
    • Add u to path and visited.
    • DFS neighbors. If any fails, return False.
    • Remove u from path and append u to a Result List.
  4. Call DFS for all unvisited nodes. Reverse the result list.

Pattern: DFS Topological Sort

⏱ O(V + E) - Visits each node and edge once.💾 O(V + E) - Adjacency list and recursion depth.

Detailed Dry Run

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

CallPathResultAction
DFS(0){0}[]Visit 1
DFS(1){0,1}[1]No neighbors, backtrack
-{0}[1,0]Done with 0
Reverse [1,0] -> [0,1]
java
class Solution {
    public int[] findOrder(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
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            if (hasCycle(i, adj, visited, res)) return new int[0];
        }
        Collections.reverse(res);
        return res.stream().mapToInt(i -> i).toArray();
    }
    private boolean hasCycle(int u, List<Integer>[] adj, int[] visited, List<Integer> res) {
        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, res)) return true;
        visited[u] = 2;
        res.add(u);
        return false;
    }
}
Approach 2

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

Intuition

Kahn's algorithm uses the concept of in-degrees (number of incoming edges). Nodes with 0 in-degree are ready to be taken. We repeatedly take such nodes and 'remove' their outgoing edges, potentially creating new 0 in-degree nodes.

Thought Process

  1. Calculate indegree for all nodes.
  2. Add all nodes with indegree == 0 to a Queue.
  3. While queue is not empty:
    • Pop u, add it to the result list.
    • For each neighbor v of u:
      • Decrement indegree[v].
      • If indegree[v] == 0, add v to queue.
  4. If result length == numCourses, return it; otherwise, a cycle exists.

Pattern: Topological Sort (BFS)

⏱ O(V + E) - Standard traversal.💾 O(V + E) - For adjacency list and indegree mapping.

Detailed Dry Run

2 courses, 1 -> 0

  1. Indegrees: {0:1, 1:0}
  2. Queue: [1]
  3. Pop 1, Res: [1], Indegree 0 becomes 0, Queue [0]
  4. Pop 0, Res: [1, 0] Result: [1, 0]
java
class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        int[] indegree = new int[numCourses];
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) adj.add(new ArrayList<>());
        for (int[] p : prerequisites) {
            adj.get(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[] res = new int[numCourses];
        int count = 0;
        while (!q.isEmpty()) {
            int curr = q.poll();
            res[count++] = curr;
            for (int neighbor : adj.get(curr)) {
                if (--indegree[neighbor] == 0) q.add(neighbor);
            }
        }
        return count == numCourses ? res : new int[0];
    }
}
← Previous QuestionRotting Oranges
Next Question →Graph Valid Tree