Pseudo-code:

text
function solve_brute_force(n, prerequisites):
    permutations = generate_all_permutations(0 to n-1)
    for perm in permutations:
        valid = true
        for [a, b] in prerequisites:
            if index_of(b, perm) > index_of(a, perm):
                valid = false
                break
        if valid:
            return perm
    return []

Why this fails: The time complexity of generating all permutations is $O(N!)$. For $N=2000$ (the constraint in this problem), $2000!$ is an astronomically large number, far exceeding the computational limits of any machine. This approach will result in a Time Limit Exceeded (TLE) error immediately.

Core Insight for Course Schedule II

The core insight for solving LeetCode 210 lies in understanding that the problem asks for a Topological Sort of a directed graph. A valid topological ordering is a linear ordering of vertices such that for every directed edge $u \to v$, vertex $u$ comes before $v$ in the ordering.

The critical constraint is that a topological sort is impossible if the graph contains a cycle. Therefore, our algorithm must serve two purposes simultaneously:

1. Cycle Detection: Ensure no circular dependencies exist.
2. Ordering: Construct the list of courses in the correct order.

To achieve this efficiently, we use Depth-First Search (DFS) with Three-Color States. Instead of a simple boolean visited array, we track the state of each node during the traversal:

• State 0 (Unvisited): The node has not been processed yet.
• State 1 (Visiting): The node is currently in the recursion stack (being processed). If we encounter a node in this state, we have found a cycle (a back edge).
• State 2 (Visited): The node and all its descendants have been fully processed and added to the result.

Visual Description: Imagine the DFS traversal as a path being drawn through the graph. When we move from node A to node B, we mark A as "Visiting". If the path eventually leads back to A while A is still marked "Visiting", we have closed a loop, indicating a cycle. If we finish processing all neighbors of B without finding a cycle, we mark B as "Visited" and verify that it is safe to add to our schedule. The order in which nodes are marked "Visited" (State 2) gives us the reverse topological order.

Algorithm Strategy: Graph DFS - Cycle Detection

1. Graph Construction: Convert the input prerequisites list into an adjacency list. Note that an input [a, b] means an edge exists from b to a (b must be taken before a).
2. State Initialization: Initialize an array state of size numCourses with all values set to 0 (Unvisited).
3. Result Container: Use a dynamic array or list to store the topological sort.
4. Outer Loop: Iterate through every course from 0 to numCourses - 1. If a course is in State 0, initiate a DFS traversal from that node. This handles disconnected graph components.
5. DFS Function:
   • If the current node is State 1 (Visiting), a cycle is detected. Return false.
   • If the current node is State 2 (Visited), it is already processed. Return true.
   • Mark the current node as State 1.
   • Recursively visit all neighbors. If any recursive call returns false, propagate the failure up the stack.
   • After visiting all neighbors successfully, mark the current node as State 2 (Visited).
   • Append the node to the result list.
6. Final Processing: Since DFS finishes the deepest nodes first (post-order traversal), the result list will contain courses in reverse topological order (children before parents). Reverse the list to get the correct order.
7. Output: If a cycle was detected at any point, return an empty array. Otherwise, return the reversed list.

Execution Flow

Let's trace the algorithm with numCourses = 4 and prerequisites = [[1,0], [2,0], [3,1], [3,2]]. Edges: $0 \to 1$, $0 \to 2$, $1 \to 3$, $2 \to 3$.

1. Init: state = [0, 0, 0, 0], result = [].
2. Outer Loop: Start at node 0 (State 0). Call dfs(0).
3. dfs(0):
   • Mark 0 as State 1.
   • Neighbors of 0 are 1 and 2.
   • Call dfs(1):
     • Mark 1 as State 1.
     • Neighbor of 1 is 3.
     • Call dfs(3):
       • Mark 3 as State 1.
       • No neighbors.
       • Mark 3 as State 2.
       • Add 3 to result. result = [3].
       • Return true.
     • Mark 1 as State 2.
     • Add 1 to result. result = [3, 1].
     • Return true.
   • Call dfs(2):
     • Mark 2 as State 1.
     • Neighbor of 2 is 3.
     • Call dfs(3):
       • 3 is State 2 (Visited). Return true.
     • Mark 2 as State 2.
     • Add 2 to result. result = [3, 1, 2].
     • Return true.
   • Mark 0 as State 2.
   • Add 0 to result. result = [3, 1, 2, 0].
   • Return true.
4. Outer Loop: Nodes 1, 2, 3 are already State 2. Skip.
5. Finalize: Reverse result to get [0, 2, 1, 3]. This is a valid topological order.

Proof of Correctness

The correctness of this algorithm relies on the properties of Depth-First Search on a DAG.

1. Cycle Detection: By marking nodes as "Visiting" (State 1) upon entry and "Visited" (State 2) upon exit, any edge pointing to a "Visiting" node represents a back-edge to an ancestor in the current recursion stack. This is the definition of a cycle in DFS. If such an edge is found, the algorithm correctly identifies that no topological sort exists.
2. Ordering: In a DFS, a node is marked "Visited" and added to the list only after all its reachable descendants have been processed (post-order traversal). This means for any edge $u \to v$, $v$ will be added to the list before $u$. Consequently, the list represents a reverse topological order. Reversing this list guarantees that for every edge $u \to v$, $u$ appears before $v$, satisfying the problem constraints.

Reference Implementation

C++ Solution for LeetCode 210

cpp
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    // 0 = Unvisited, 1 = Visiting, 2 = Visited
    bool dfs(int node, vector<vector<int>>& adj, vector<int>& state, vector<int>& result) {
        if (state[node] == 1) return false; // Cycle detected
        if (state[node] == 2) return true;  // Already processed
        
        state[node] = 1; // Mark as visiting
        
        for (int neighbor : adj[node]) {
            if (!dfs(neighbor, adj, state, result)) {
                return false;
            }
        }
        
        state[node] = 2; // Mark as visited
        result.push_back(node); // Add to result (post-order)
        return true;
    }

    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> adj(numCourses);
        // Build adjacency list: [a, b] means b -> a
        for (const auto& edge : prerequisites) {
            adj[edge[1]].push_back(edge[0]);
        }
        
        vector<int> state(numCourses, 0);
        vector<int> result;
        
        for (int i = 0; i < numCourses; ++i) {
            if (state[i] == 0) {
                if (!dfs(i, adj, state, result)) {
                    return {}; // Cycle detected, return empty
                }
            }
        }
        
        reverse(result.begin(), result.end());
        return result;
    }
};

Java Solution for LeetCode 210

java
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
    // 0 = Unvisited, 1 = Visiting, 2 = Visited
    private boolean dfs(int node, List<List<Integer>> adj, int[] state, List<Integer> result) {
        if (state[node] == 1) return false; // Cycle detected
        if (state[node] == 2) return true;  // Already processed
        
        state[node] = 1; // Mark as visiting
        
        for (int neighbor : adj.get(node)) {
            if (!dfs(neighbor, adj, state, result)) {
                return false;
            }
        }
        
        state[node] = 2; // Mark as visited
        result.add(node); // Add to result (post-order)
        return true;
    }

    public int[] findOrder(int numCourses, int[][] prerequisites) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            adj.add(new ArrayList<>());
        }
        
        // Build adjacency list: [a, b] means b -> a
        for (int[] edge : prerequisites) {
            adj.get(edge[1]).add(edge[0]);
        }
        
        int[] state = new int[numCourses];
        List<Integer> resultList = new ArrayList<>();
        
        for (int i = 0; i < numCourses; i++) {
            if (state[i] == 0) {
                if (!dfs(i, adj, state, resultList)) {
                    return new int[0]; // Cycle detected
                }
            }
        }
        
        // Reverse to get topological order
        Collections.reverse(resultList);
        
        // Convert List to int[]
        int[] result = new int[numCourses];
        for (int i = 0; i < numCourses; i++) {
            result[i] = resultList.get(i);
        }
        
        return result;
    }
}

Python Solution for LeetCode 210

python
from collections import defaultdict

class Solution:
    def findOrder(self, numCourses: int, prerequisites: list[list[int]]) -> list[int]:
        adj = defaultdict(list)
        # Build adjacency list: [a, b] means b -> a
        for dest, src in prerequisites:
            adj[src].append(dest)
            
        # 0 = Unvisited, 1 = Visiting, 2 = Visited
        state = [0] * numCourses
        result = []
        
        def dfs(node):
            if state[node] == 1:
                return False # Cycle detected
            if state[node] == 2:
                return True  # Already processed
            
            state[node] = 1 # Mark as visiting
            
            for neighbor in adj[node]:
                if not dfs(neighbor):
                    return False
            
            state[node] = 2 # Mark as visited
            result.append(node) # Add to result (post-order)
            return True
            
        for i in range(numCourses):
            if state[i] == 0:
                if not dfs(i):
                    return []
                    
        return result[::-1] # Reverse to get topological order