你这个学期必须选修 numCourse 门课程,记为 0 到 numCourse-1 。
在选修某些课程之前需要一些先修课程。 例如,想要学习课程 0 ,你需要先完成课程 1 ,我们用一个匹配来表示他们:[0,1]
给定课程总量以及它们的先决条件,请你判断是否可能完成所有课程的学习?
示例1:
输入: 2, [[1,0]]
输出: true
解释: 总共有 2 门课程。学习课程 1 之前,你需要完成课程 0。所以这是可能的。
示例2:
输入: 2, [[1,0],[0,1]]
输出: false
解释: 总共有 2 门课程。学习课程 1 之前,你需要先完成课程 0;并且学习课程 0 之前,你还应先完成课程 1。这是不可能的。
提示:
1 <= numCourses <= 10^5
转载自https://leetcode-cn.com/problems/course-schedule/solution/course-schedule-tuo-bu-pai-xu-bfsdfsliang-chong-fa/
课程安排图问题,可以转化为通过拓扑排序判断这个图是否是有向无环图
拓扑排序的原理:可见这篇文章 (opens new window)
方法1、入度表(BFS):
算法流程:
indegrees
。queue
,将所有入度为 0 的节点入队。queue
非空时,依次将队首节点出队,在课程安排图中删除此节点pre
: pre
,而是将此节点对应所有邻接节点cur
的入度 -1,即indegrees[cur] -= 1
。cur
的入度为 0,说明 cur
所有的前驱节点已经被 “删除”,此时将 cur
入队。pre
出队时,执行 numCourses--
; numCourses == 0
判断课程是否可以成功安排。复杂度分析:
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
int[] indegrees = new int[numCourses];
List<List<Integer>> adjacency = new ArrayList<>();
Queue<Integer> queue = new LinkedList<>();
for(int i=0;i<numCourses;i++){
adjacency.add(new ArrayList<>());
}
// 获得每个课程入度和邻接表
for(int[] cp:prerequisites){
indegrees[cp[0]]++;
adjacency.get(cp[1]).add(cp[0]);
}
// 获得所有入度为0的课程
for(int i=0;i<numCourses;i++){
if(indegrees[i]==0) queue.add(i);
}
// BFS
while(!queue.isEmpty()){
int pre = queue.poll();
numCourses--;
for(int cur: adjacency.get(pre)){
if(--indegrees[cur]==0) queue.add(cur);
}
}
return numCourses == 0;
}
}