课程表

原题链接

使用的方法

拓扑排序

解题思路

• 给定一个整数 numCourses 和一个数组 prerequisites，其中 prerequisites[i] = [a_i, b_i] 表示要学习课程 a_i 需要先学习课程 b_i。我们需要判断是否可能完成所有课程的学习。
• 这个问题可以看作是一个有向图的拓扑排序问题。我们可以将课程看作图中的节点，prerequisites 中的每个关系 [a_i, b_i] 表示从节点 b_i 到节点 a_i 的有向边。我们需要判断这个有向图是否存在环，如果存在环，则无法完成所有课程的学习。
• 我们可以使用入度数组来记录每个节点的入度，即有多少条边指向该节点。我们首先构建图和入度数组，然后将所有入度为 0 的节点加入队列，表示这些课程可以直接学习。
• 接下来，我们从队列中依次取出节点，表示我们学习了这门课程。对于每个被学习的课程，我们将其指向的课程的入度减 1，如果某个课程的入度变为 0，说明它也可以被学习了，我们将其加入队列。
• 最后，我们统计已经学习了多少门课程，如果这个数量等于 numCourses，说明我们可以完成所有课程的学习；否则，说明存在环，无法完成所有课程的学习。

代码实现

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<List<Integer>> graph = new ArrayList<>();
        for(int i=0;i<numCourses;i++){
            graph.add(new ArrayList<>());
        }
        // 入度数组
        int[] inDegree = new int[numCourses]; 
        for(int[] pre : prerequisites){
            int a = pre[0];
            int b = pre[1];
            graph.get(b).add(a); // 把 a 加到 b 对应的列表中，b -> a
            inDegree[a]++;
        }

        // 存放当前可以直接学习的课程
        Queue<Integer> queue = new LinkedList<>();
        // 即入度为0的课程
        for(int i = 0;i < numCourses;i++){
            if(inDegree[i] == 0){
                queue.offer(i);
            }
        }
        
        int count = 0; // 记录已经学了多少门课程
        while(!queue.isEmpty()){ // 队列不为空，代表还存在能够学习的课程
            int course = queue.poll(); // 从队列中拿出一门可以学的课
            count++;
            for(int next : graph.get(course)){
                inDegree[next]--;// 课程学完，入度-1
                if(inDegree[next] == 0) // 重新对入度进行判断
                    queue.offer(next); 
            }
        }
        return count == numCourses;
    }
}