课程表 II【LC210】
现在你总共有 numCourses 门课需要选，记为 0 到 numCourses - 1。给你一个数组 prerequisites ，其中 prerequisites[i] = [ai, bi] ，表示在选修课程 ai 前 必须 先选修 bi 。
例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示：[0,1] 。
返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，你只要返回 任意一种 就可以了。如果不可能完成所有课程，返回 一个空数组 。
- 思路：拓扑排序
由于在选修课程ai前 必须 先选修bi，因此我们可以构建一条由bi指向ai的边，然后使用拓扑排序，优先遍历入度为0的节点，并将其加入拓扑排序数组中，如果最后数组的大小与节点个数不相同，那么证明有向图中有环存在，不可能完成所有课程 - 实现
class Solution { public int[] findOrder(int numCourses, int[][] prerequisites) { int[] inDeg = new int[numCourses]; List<Integer>[] g = new ArrayList[numCourses]; Arrays.setAll(g, e -> new ArrayList<>()); for (int[] p : prerequisites){ int u = p[1], v = p[0]; g[u].add(v); inDeg[v]++; } Deque<Integer> queue = new LinkedList<>(); List<Integer> order = new ArrayList<>(); for (int i = 0; i < numCourses; i++){ if (inDeg[i] == 0){ queue.addLast(i); } } while (!queue.isEmpty()){ int u = queue.pollFirst(); order.add(u); for (int v : g[u]){ inDeg[v]--; if (inDeg[v] == 0){ queue.addLast(v); } } } return order.size() == numCourses ? order.stream().mapToInt(x -> x).toArray() : new int[]{}; } }
复杂度
时间复杂度：O ( E + V ) ，E表示邻边的跳数，V为结点的个数
空间复杂度：O ( V )
