// Runtime: 76 ms, faster than 5.08% of Java online submissions for Course Schedule II.
// Memory Usage: 48.5 MB, less than 8.54% of Java online submissions for Course Schedule II.
class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        boolean[][] g = new boolean[numCourses][numCourses];
        for (int[] req: prerequisites) g[req[0]][req[1]] = true;

        int[] depths = new int[numCourses];
        boolean[] visited = new boolean[numCourses];
        try {
            for (int v = 0; v < numCourses; v++) findDepth(v, numCourses, g, depths, visited);
        }
        catch (IllegalStateException e) {
            return new int[0];
        }

        List<Integer> res = new ArrayList<>();
        for (int v = 0; v < numCourses; v++) res.add(v);

        Collections.sort(res, (a, b) -> depths[a] - depths[b]);

        int[] result = new int[numCourses];
        for (int i = 0; i < numCourses; i++) result[i] = res.get(i);
        return result;
    }

    private int findDepth(int v, int numCourses, boolean[][] g, int[] depths, boolean[] visited) {
        if (depths[v] > 0) return depths[v];

        if (visited[v]) throw new IllegalStateException();

        visited[v] = true;

        int maxChildDepth = 0;
        for (int t = 0; t < numCourses; t++) {
            if (t == v) continue;
            if (!g[v][t]) continue;

            maxChildDepth = Math.max(maxChildDepth, findDepth(t, numCourses, g, depths, visited));
        }

        visited[v] = false;

        int depth = maxChildDepth + 1;
        depths[v] = depth;
        return depth;
    }
}