Course Schedule II

1public int[] findOrder(int numCourses, int[][] prerequisites) {
2    // Build adjacency list
3    List<List<Integer>> graph = new ArrayList<>();
4    for (int i = 0; i < numCourses; i++) {
5        graph.add(new ArrayList<>());
6    }
7    for (int[] prereq : prerequisites) {
8        graph.get(prereq[1]).add(prereq[0]);
9    }
10
11    // 0: unvisited, 1: visiting, 2: visited
12    int[] state = new int[numCourses];
13    List<Integer> result = new ArrayList<>();
14
15    for (int i = 0; i < numCourses; i++) {
16        if (state[i] == 0) {
17            if (!dfs(i, graph, state, result)) {
18                return new int[0];  // Cycle detected
19            }
20        }
21    }
22
23    Collections.reverse(result);
24    return result.stream().mapToInt(i -> i).toArray();
25}
26
27private boolean dfs(int course, List<List<Integer>> graph,
28                    int[] state, List<Integer> result) {
29    if (state[course] == 1) return false;  // Cycle
30    if (state[course] == 2) return true;   // Visited
31
32    state[course] = 1;  // Mark as visiting
33
34    for (int dependent : graph.get(course)) {
35        if (!dfs(dependent, graph, state, result)) {
36            return false;
37        }
38    }
39
40    state[course] = 2;  // Mark as visited
41    result.add(course);
42    return true;
43}