课程表【LC207】
你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。
例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。
- 思路
由于在选修课程ai前 必须 先选修bi，因此我们可以构建一条由bi指向ai的边，然后使用拓扑排序，优先遍历入度为0的节点，并将其加入拓扑排序数组中，如果最后数组的大小与节点个数不相同，那么证明有向图中有环存在，不可能完成所有课程 - 实现
class Solution { public boolean canFinish(int numCourses, int[][] prerequisites) { Deque<Integer> queue = new LinkedList<>(); int[] inDeg = new int[numCourses]; List<Integer>[] after = new List[numCourses]; Arrays.setAll(after, e -> new ArrayList<>()); for (int[] pre : prerequisites){ inDeg[pre[0]]++; after[pre[1]].add(pre[0]); } List<Integer> sorted = new ArrayList<>(); for (int i = 0; i < numCourses; i++){ if (inDeg[i] == 0){ queue.addLast(i); } } while(!queue.isEmpty()){ int x = queue.pollFirst(); sorted.add(x); for (int y : after[x]){ inDeg[y]--; if (inDeg[y] == 0){ queue.addLast(y); } } } return sorted.size() == numCourses; } }
复杂度
时间复杂度：O ( E + V )，E表示邻边的跳数，V为结点的个数
空间复杂度：O ( V )
