题目
你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi。
- 例如，先修课程对
[0, 1]表示：想要学习课程0，你需要先完成课程1。
请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。
代码
import java.util.*;
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
// 1. 初始化入度数组 和 邻接表
int[] inDegree = new int[numCourses];
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < numCourses; i++) {
adj.add(new ArrayList<>());
}
// 2. 填充邻接表和入度
for (int[] pre : prerequisites) {
int ai = pre[0]; // 目标课程
int bi = pre[1]; // 先修课程，边：bi -> ai
adj.get(bi).add(ai); // bi 的后继课程列表添加 ai
inDegree[ai]++; // ai 的入度（先修数量）+1
}
// 3. 队列：存入所有入度为0、可以直接学习的课程
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < numCourses; i++) {
if (inDegree[i] == 0) {
queue.offer(i);
}
}
// 4. BFS 拓扑排序
int count = 0;
while (!queue.isEmpty()) {
int cur = queue.poll();
count++; // 学完一门课，计数+1
// 遍历当前课程的所有后继课程
for (int next : adj.get(cur)) {
inDegree[next]--;
// 后继课程的先修全部完成，可以学习了
if (inDegree[next] == 0) {
queue.offer(next);
}
}
}
// 5. 学完的课程数等于总课程数 → 无环，可以修完
return count == numCourses;
}
}