LeetCode 207. 课程表

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