Course Schedule II

1public int[] findOrder(int numCourses, int[][] prerequisites) {
2    List<List<Integer>> graph = new ArrayList<>();
3    for (int i = 0; i < numCourses; i++) {
4        graph.add(new ArrayList<>());
5    }
6    for (int[] edge : prerequisites) {
7        graph.get(edge[1]).add(edge[0]);
8    }
9
10    List<Integer> result = new ArrayList<>();
11    boolean[] visited = new boolean[numCourses];
12    boolean[] visiting = new boolean[numCourses];
13
14    for (int i = 0; i < numCourses; i++) {
15        if (!visited[i]) {
16            if (!dfs(i, graph, result, visited, visiting)) {
17                return new int[0];
18            }
19        }
20    }
21
22    Collections.reverse(result);
23    return result.stream().mapToInt(Integer::intValue).toArray();
24}
25
26private boolean dfs(int current, List<List<Integer>> graph, List<Integer> result,
27                    boolean[] visited, boolean[] visiting) {
28    if (visited[current]) {
29        return true;
30    }
31
32    // Cycle detected
33    if (visiting[current]) {
34        return false;
35    }
36
37    visiting[current] = true;
38    List<Integer> neighbors = graph.get(current);
39    for (int neighbor : neighbors) {
40        if (!dfs(neighbor, graph, result, visited, visiting)) {
41            return false;
42        }
43    }
44
45    visited[current] = true;
46    visiting[current] = false;
47    result.add(current);
48    return true;
49}