拓扑排序

    /**
     * LeetCode 210. Course Schedule II
     *
     * @param numCourses    课程数
     * @param prerequisites 课程先修关系
     * @return 课程学习顺序
     */
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        int[] path = new int[numCourses];
        List<Integer>[] graph = buildGraph(numCourses, prerequisites);
        // build indegree array
        int[] indegree = new int[numCourses];
        for (int i = 0; i < numCourses; i++) {
            List<Integer> list = graph[i];
            for (int to : list) {
                indegree[to]++;
            }
        }
 
        // add nodes that in degree equals 0
        Deque<Integer> deque = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (indegree[i] == 0) {
                deque.add(i);
            }
        }
 
        int count = 0;
        while (!deque.isEmpty()) {
            int curr = deque.pop();
            path[count] = curr;
            count++;
            for (int child : graph[curr]) {
                indegree[child]--;
                if (indegree[child] == 0) {
                    deque.add(child);
                }
            }
        }
 
        return count == numCourses ? path : new int[]{};
    }
 
    public List<Integer>[] buildGraph(int numCourses, int[][] prerequisites) {
        List<Integer>[] res = new LinkedList[numCourses];
        for (int i = 0; i < numCourses; i++) {
            res[i] = new LinkedList<>();
        }
        for (int[] pair : prerequisites) {
            res[pair[1]].add(pair[0]);
        }
        return res;
    }