本文最后更新于 390 天前，其中的信息可能已经有所发展或是发生改变。
题目描述：
你总共需要上 numCourses 门课，课程编号依次为 0 到 numCourses-1 。你会得到一个数组 prerequisite ，其中 prerequisites[i] = [ai, bi] 表示如果你想选 bi 课程，你 必须 先选 ai 课程。
- 有的课会有直接的先修课程，比如如果想上课程
1，你必须先上课程0，那么会以[0,1]数对的形式给出先修课程数对。
先决条件也可以是 间接 的。如果课程 a 是课程 b 的先决条件，课程 b 是课程 c 的先决条件，那么课程 a 就是课程 c 的先决条件。
你也得到一个数组 queries ，其中 queries[j] = [uj, vj]。对于第 j 个查询，您应该回答课程 uj 是否是课程 vj 的先决条件。
返回一个布尔数组 answer ，其中 answer[j] 是第 j 个查询的答案。
示例 1：
输入：numCourses = 2, prerequisites = [[1,0]], queries = [[0,1],[1,0]]
输出：[false,true]
解释：课程 0 不是课程 1 的先修课程，但课程 1 是课程 0 的先修课程。
示例 2：
输入：numCourses = 2, prerequisites = [], queries = [[1,0],[0,1]]
输出：[false,false]
解释：没有先修课程对，所以每门课程之间是独立的。
示例 3：
输入：numCourses = 3, prerequisites = [[1,2],[1,0],[2,0]], queries = [[1,0],[1,2]]
输出：[true,true]
提示：
2 <= numCourses <= 1000 <= prerequisites.length <= (numCourses * (numCourses - 1) / 2)prerequisites[i].length == 20 <= ai, bi <= n - 1ai != bi- 每一对
[ai, bi]都 不同 - 先修课程图中没有环。
1 <= queries.length <= 1040 <= ui, vi <= n - 1ui != vi
解法一：Flody 算法
算法思路：
Flody 算法：
Floyd 算法，也称为 Floyd-Warshall 算法，是一种用于求解所有节点对最短路径的动态规划算法。它可以在有向图或带权图中找到任意两个节点之间的最短路径。
Floyd算法的基本思想是通过中转节点逐步更新节点对之间的最短路径。它维护一个二维数组dist，其中dist[i][j]表示节点i到节点j之间的最短路径长度。
算法的具体步骤如下：
- 初始化
dist数组，将所有节点对之间的距离初始化为正无穷，但对角线上的元素（即dist[i][i]）初始化为0。 - 遍历图中的每个节点
k，作为中转节点。对于每对节点i和j，如果通过节点k可以使路径长度更短，即dist[i][k] + dist[k][j] < dist[i][j]，则更新dist[i][j] = dist[i][k] + dist[k][j]。 - 重复步骤2，直到遍历完所有节点作为中转节点。最终，
dist数组中存储的就是每对节点之间的最短路径长度。
Floyd算法的时间复杂度为 O(V ^ 3)，其中 V 是图中节点的数量。它适用于解决任意两个节点之间的最短路径问题，包括负权边或负权环的情况。
对于本题：
- 我们创建一个二维数组 pre, 其中 pre[i] [j] 表示节点 i 到节点 j 是否可达。
- 对于数组 prerequisites 中的每一项[a, b], 我们都将 pre[a] [b] 设置为 true。
- 接下来使用 Floyd 算法计算出节点之间的可达性。
- 在计算完所有节点对之间的可达性后，对于每一个查询 [a, b]，我们之间返回 pre[a] [b]即可。
代码实现：
class Solution {
public List<Boolean> checkIfPrerequisite(int numCourses, int[][] prerequisites, int[][] queries) {
boolean[][] pre = new boolean[numCourses][numCourses];
for(int[] p : prerequisites){
pre[p[0]][p[1]] = true;
}
for(int k = 0; k<numCourses;k++){
for(int i = 0;i<numCourses;i++){
for(int j = 0; j < numCourses; j++){
pre[i][j] |= pre[i][k] && pre[k][j];
}
}
}
List<Boolean> ans = new ArrayList<>();
for(int[] q : queries){
ans.add(pre[q[0]][q[1]]);
}
return ans;
}
}
复杂度分析：
时间复杂度： O(n ^ 3)
空间复杂度： O(n ^ 2)
解法二：拓扑排序 + BFS
算法思路：
本题与 207. 课程表 – 拓扑排序 210. 课程表 II – 拓扑排序 解法思路基本一致，不同之处在于：
- 创建一个二维数组 pre, 其中 pre[i] [j] 表示节点 i 到节点 j 是否可达。
- 在遍历邻接表的同时计算课程对之间的可达性。
代码实现：
class Solution {
public List<Boolean> checkIfPrerequisite(int numCourses, int[][] prerequisites, int[][] queries) {
int[] inDegree = new int[numCourses]; // 入度数组
HashMap<Integer, List<Integer>> map = new HashMap<>(); // 邻接表
boolean[][] pre = new boolean[numCourses][numCourses]; // 节点对可达性
// 构建入度数组和邻接表
for (int i = 0; i < prerequisites.length; i++) {
inDegree[prerequisites[i][0]]++; // 求课的初始入度值
if (map.containsKey(prerequisites[i][1])) { // 当前课已经存在于邻接表
map.get(prerequisites[i][1]).add(prerequisites[i][0]); // 添加依赖它的后续课
} else { // 当前课不存在于邻接表
List<Integer> list = new ArrayList<>();
list.add(prerequisites[i][0]);
map.put(prerequisites[i][1], list);
}
}
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < inDegree.length; i++) { // 所有入度为0的课入列
if (inDegree[i] == 0) {
queue.offer(i);
}
}
while (!queue.isEmpty()) {
int selected = queue.poll(); // 当前选的课，出列
List<Integer> toEnQueue = map.get(selected); // 获取这门课对应的后续课
if (toEnQueue != null && !toEnQueue.isEmpty()) { // 确实有后续课
for (int i = 0; i < toEnQueue.size(); i++) {
int dependentCourse = toEnQueue.get(i);
// 记录课程之间的可达性
pre[selected][dependentCourse] = true;
for(int h = 0; h < numCourses; h++){
pre[h][dependentCourse] |= pre[h][selected];
}
inDegree[dependentCourse]--; // 依赖它的后续课的入度-1
if (inDegree[dependentCourse] == 0) { // 如果因此减为0，入列
queue.offer(dependentCourse);
}
}
}
}
List<Boolean> ans = new ArrayList<>();
for(int[] q : queries){
ans.add(pre[q[1]][q[0]]);
}
return ans;
}
}
复杂度分析：
时间复杂度： O(n ^ 2)
空间复杂度： O(n ^ 2)
