207. 课程表#

课程数：4
依赖关系：[[1,0], [2,1], [3,2]]

Step 1: 构建邻接表和入度数组
课程0 → 被课程1依赖
课程1 → 被课程2依赖
课程2 → 被课程3依赖

入度统计：
课程0：0个依赖
课程1：1个依赖（依赖0）
课程2：1个依赖（依赖1）
课程3：1个依赖（依赖2）

Step 2: BFS遍历过程
第一轮：
- 入度为0的课程：[0]
- 将0加入队列
- 学习0后，课程1的入度减1（变为0）

第二轮：
- 入度为0的课程：[1]
- 将1加入队列
- 学习1后，课程2的入度减1（变为0）

第三轮：
- 入度为0的课程：[2]
- 将2加入队列
- 学习2后，课程3的入度减1（变为0）

第四轮：
- 入度为0的课程：[3]
- 将3加入队列
- 没有更多依赖需要解除

最终顺序：0 → 1 → 2 → 3
学习课程总数：4（等于课程总数，说明可行）

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // adjacency：邻接表，adjacency[x] 存放“依赖课程 x 的所有课程”
        // 例如 x -> y 表示学完 x 后可以解锁 y
        List<List<Integer>> adjacency = new ArrayList<>();
        // 为每门课程初始化一个空的后续课程列表
        for (int i = 0; i < numCourses; i++) {
            adjacency.add(new ArrayList<>());
        }

        // inDegrees[i]：课程 i 当前还有多少前置课程未完成（入度）
        int[] inDegrees = new int[numCourses];

        // 根据 prerequisites 构建图结构和入度数组
        for (int[] pre : prerequisites) {
            // curr：要学习的课程（被依赖课程）
            int curr = pre[0];
            // prev：curr 的前置课程（先修课程）
            int prev = pre[1];
            // 建边 prev -> curr，表示“学完 prev 才能学 curr”
            adjacency.get(prev).add(curr);
            // curr 多了一个前置依赖，入度加 1
            inDegrees[curr]++;
        }

        // queue：拓扑排序的 BFS 队列，先放入所有“当前可直接学习”的课程（入度为 0）
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (inDegrees[i] == 0) {
                // 没有任何前置依赖，可立即学习
                queue.offer(i);
            }
        }

        // count：记录已经“成功学习并出队”的课程数量
        int count = 0;
        // 开始 BFS 拓扑遍历
        while (!queue.isEmpty()) {
            // 取出一门当前可学习的课程
            int course = queue.poll();
            // 这门课程被学习完成，计数加 1
            count++;

            // 遍历所有依赖当前课程的后续课程
            for (int next : adjacency.get(course)) {
                // 当前课程学完后，next 少了一个未完成前置条件
                inDegrees[next]--;
                // 如果 next 的入度降到 0，说明它现在也可以学习了，入队
                if (inDegrees[next] == 0) {
                    queue.offer(next);
                }
            }
        }

        // 若 count == numCourses，说明所有课程都能按某种顺序学完（无环）
        // 否则说明图中存在环，至少有一批课程永远无法把入度降到 0
        return count == numCourses;
    }
}