1、题目
课程表 - 力扣（LeetCode） https://leetcode-cn.com/problems/course-schedule/
2、题解
这道题的思路其实很简单，排除了不满足的情况自然就满足了
首先，如果学习次数少于课程数量，就一定不能满足。
其次，如果将各个课程看成一个个的节点，节点的先决关系就是两点之间的连线，而且是有方向的连线。这样就课程和课程之间的关系就形成了一个有向图。但凡有向图中有两点间存在方向相反的两条线，即A->B 且B->A成立，那么基于类似死锁这样的情况，我们就无法学完当前的课程。
那么我们只需要判断当前数据代表的有向图是否存在环即可；
3、代码
public class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
int[] inDegree = new int[numCourses];
int[][] graph = new int[numCourses][numCourses];
for(int i = 0; i < prerequisites.length; i++){
graph[prerequisites[i][1]][prerequisites[i][0]] = 1;
inDegree[prerequisites[i][0]]++;
}
//定义一个队列Q，并把所有入度为0的节点加入队列。
Queue<Integer> queue = new LinkedList<>();
for(int i = 0; i < numCourses; i++){
if(inDegree[i] == 0){
queue.add(i);
}
}
//取队首节点，输出。然后删去所有从它出发的边，并令这些边到达的顶点的入度减1，如果某个顶点的入度减为0，则将其加入队列。
int num = 0;
while(!queue.isEmpty()){
int u = queue.poll();
for(int v = 0; v < numCourses; v++){
if(graph[u][v] != 0){
inDegree[v]--;
if(inDegree[v] == 0){
queue.add(v);
}
}
}
num++;
}
return num == numCourses;
}
}
4、执行结果
image.png
