1. 题目

读题

考查点

2. 解法

思路

这道题的解答思路是使用拓扑排序来判断有向图是否有环，如果有环，说明无法完成所有课程，如果没有环，输出拓扑排序的结果。拓扑排序的基本思想是从有向图中选择一个没有前驱（即入度为0）的顶点并输出，然后从图中删除该顶点和所有以它为起点的有向边，重复这一步骤直到所有顶点均已输出，或者当前图中不存在无前驱的顶点为止。后一种情况说明有向图中必然存在环。

拓扑排序可以用深度优先搜索或者广度优先搜索来实现。深度优先搜索的方法是对每个未访问的节点，执行以下操作：

标记当前节点为访问中
递归访问当前节点的所有邻接节点，如果发现已经访问过或者正在访问中的节点，说明存在环，返回false
标记当前节点为已访问，并将其加入结果栈
返回true

广度优先搜索的方法是维护一个队列和一个入度数组，入度数组记录每个节点的前驱节点个数。初始时，将所有入度为0的节点加入队列，并将其加入结果列表。然后执行以下操作：

从队列中弹出一个节点
遍历该节点的所有邻接节点，将其入度减一
如果某个邻接节点的入度变为0，将其加入队列，并将其加入结果列表
重复以上步骤直到队列为空

如果结果列表的长度等于课程数，说明可以完成所有课程，否则说明存在环。

代码逻辑

具体实现

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        // 邻接表
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            adj.add(new ArrayList<>());
        }
        // 入度数组
        int[] indegrees = new int[numCourses];
        // 遍历先决条件，构建邻接表和入度数组
        for (int[] p : prerequisites) {
            adj.get(p[1]).add(p[0]);
            indegrees[p[0]]++;
        }
        // 结果数组
        int[] res = new int[numCourses];
        // 记录结果数组的索引
        int index = 0;
        // 队列，存放入度为0的节点
        Queue<Integer> queue = new LinkedList<>();
        // 将所有入度为0的节点入队，并加入结果数组
        for (int i = 0; i < numCourses; i++) {
            if (indegrees[i] == 0) {
                queue.offer(i);
                res[index++] = i;
            }
        }
        // 当队列不为空时，循环以下操作
        while (!queue.isEmpty()) {
            // 出队一个节点
            int cur = queue.poll();
            // 遍历该节点的邻接节点，将其入度减一
            for (int next : adj.get(cur)) {
                indegrees[next]--;
                // 如果某个邻接节点的入度变为0，将其入队，并加入结果数组
                if (indegrees[next] == 0) {
                    queue.offer(next);
                    res[index++] = next;
                }
            }
        }
        // 如果结果数组的长度等于课程数，说明可以完成所有课程，返回结果数组
        if (index == numCourses) {
            return res;
        }
        // 否则，返回一个空数组
        return new int[0];
    }
}