课程表 - LeetCode 热题 53

大家好！我是曾续缘💘

今天是《LeetCode 热题 100》系列

发车第 53 天

图论第 3 题

❤️点赞 👍 收藏 ⭐再看，养成习惯

课程表
你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。

在选修某些课程之前需要一些先修课程。先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [a_i, b_i] ，表示如果要学习课程 a_i 则必须先学习课程 b_i。

例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。

请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

示例 1：
输入：numCourses = 2, prerequisites = [[1,0]]
输出：true
解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。
示例 2：
输入：numCourses = 2, prerequisites = [[1,0],[0,1]]
输出：false
解释：总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的。
提示：

1 <= numCourses <= 2000
0 <= prerequisites.length <= 5000
prerequisites[i].length == 2
0 <= a_i, b_i < numCourses
prerequisites[i] 中的所有课程对 互不相同
难度：💖💖

解题方法

这道题目是典型的拓扑排序问题。我们需要判断是否可以完成所有课程的学习。

在拓扑排序中，首先考虑的是没有任何入边的节点，也就是没有先修课程要求的节点。将这样的节点加入拓扑排序的结果列表后，可以移除该节点的所有出边，减少相邻节点对先修课程的需求。如果某个相邻节点变成了没有任何入边的节点，那么说明这门课可以开始学习了，加入拓扑排序的结果列表。按照这个流程，持续将没有入边的节点加入拓扑排序的结果列表，直到包含所有节点（得到一种拓扑排序），如果不包含所有节点，说明图中存在环，换上的节点不能因为入边为0加入结果列表中。

具体过程如下：

首先，我们需要建立一个有向图来表示先修课程的关系。使用邻接表的形式存储图，即使用一个二维列表edges，其中edges[i]存储了课程i的后续课程。
同时，我们需要统计每门课程的入度（即有多少先修课程）。使用一个一维数组deg来记录每门课程的入度。
接下来，我们需要找到没有任何入边的节点，因为这些课程可以直接学习，没有先修课程的要求。我们将这些节点加入到拓扑排序的结果中，并将与其相邻的节点的入度减少1。
重复步骤3，直到队列为空。最后，如果拓扑排序的结果包含了所有课程，说明可以完成全部课程的学习；否则，存在环，不可能完成所有课程的学习。

Code

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<List<Integer>> edges = new ArrayList<List<Integer>>();
        for(int i = 0; i < numCourses; i++){
            edges.add(new ArrayList<Integer>());
        }
        int[] deg = new int[numCourses];
        for(int[] e : prerequisites){
            edges.get(e[1]).add(e[0]);
            deg[e[0]]++;
        }
        Queue<Integer> q = new LinkedList<Integer>();
        for(int i = 0; i < numCourses; i++){
            if(deg[i] == 0){
                q.offer(i);
            }
        }
        List<Integer> topo = new ArrayList<Integer>();
        while(!q.isEmpty()){
            int u = q.poll();
            topo.add(u);
            for(int v : edges.get(u)){
                deg[v]--;
                if(deg[v] == 0){
                    q.offer(v);
                }
            }
        }
        return topo.size() == numCourses;
    }
}