课程表【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 )