引用：labuladong的算法小抄 (opens new window)

算法思路（DFS）

把问题转化成「有向图」这种数据结构，只要图中存在环，那就说明存在循环依赖。

回溯算法的「做选择」和「撤销选择」在 for 循环里面，而 DFS 对 onPath 数组的操作在 for 循环外面。

回溯算法和 DFS 算法的区别所在：回溯算法关注的是树枝, DFS 关注的是节点。 将图后序遍历的结果进行反转，就是拓扑排序的结果。

代码实现

class Solution {
    boolean[] visited;
    boolean[] onPath;
    boolean hasCycle = false;
    List<Integer> postorder = new ArrayList();
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        // 将问题转换为图结构
        List<Integer>[] graph = buildGrapth(numCourses,prerequisites);
        // visited避免DFS走重复路线
        visited = new boolean[numCourses];
        // onPath判断是否成环
        onPath = new boolean[numCourses];
        // 并不一定是连通图，要从每个节点都尝试遍历一次
        for(int i = 0; i < numCourses; i++){
            traverse(graph, i);
        }
        if(hasCycle){
            return new int[]{};
        } else {
            Collections.reverse(postorder);
            // 图后序遍历的结果反转，就是拓扑排序的结果
            int[] res = new int[numCourses];
            for(int i = 0; i < numCourses; i++){
                res[i] = postorder.get(i);
            }
            return res;
        }
    }

    List<Integer>[] buildGrapth(int numCourses, int[][] prerequisites){
        List<Integer>[] graph = new LinkedList[numCourses];
        for(int i = 0; i < numCourses; i++){
            graph[i] = new LinkedList<>();
        }
        for(int[] edge : prerequisites){
            int from = edge[1];
            int to = edge[0];
            graph[from].add(to);
        }
        return graph;
    }

    void traverse(List<Integer>[] graph, int node){
        if(onPath[node]){
            hasCycle = true;
        }
        if(visited[node] || hasCycle){
            return;
        }
        visited[node] = true;
        onPath[node] = true;
        for(int dest : graph[node]){
            traverse(graph, dest);
        }
        postorder.add(node);
        onPath[node] = false;
    }
}