课程表 IV
难度:
标签:
题目描述
你总共需要上 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
代码结果
运行时间: 80 ms, 内存: 18.9 MB
/*
* 思路：
* 同样使用Floyd-Warshall算法，我们可以利用Java Stream API来简化某些操作。
* 首先，我们初始化一个二维布尔数组reachable，并使用Stream API来更新它。
* 然后，我们使用Floyd-Warshall算法更新reachable数组，并在此过程中使用Stream API来进行遍历。
* 最后，我们再次使用Stream API来处理查询数组，并根据reachable数组的值来回答每个查询。
*/
import java.util.stream.IntStream;
import java.util.stream.Stream;
public boolean[] checkIfPrerequisite(int numCourses, int[][] prerequisites, int[][] queries) {
boolean[][] reachable = new boolean[numCourses][numCourses];
Stream.of(prerequisites).forEach(prereq -> reachable[prereq[0]][prereq[1]] = true);
IntStream.range(0, numCourses).forEach(k ->
IntStream.range(0, numCourses).forEach(i ->
IntStream.range(0, numCourses).forEach(j -> {
if (reachable[i][k] && reachable[k][j]) {
reachable[i][j] = true;
}
})
)
);
return IntStream.range(0, queries.length)
.mapToObj(i -> reachable[queries[i][0]][queries[i][1]])
.mapToBoolean(Boolean::booleanValue)
.toArray();
}
解释
方法:
该题解使用深度优先搜索（DFS）来确定课程之间的依赖关系。首先，每个课程的入度和一个用于存储每个课程所有先决课程的集合（father）被初始化。题解将先修关系的方向反转，即如果课程u是课程v的先修，则在v到u之间建立一条边。对所有入度为0的课程，也就是没有任何先修要求的课程，执行DFS。在DFS过程中，每访问一个课程，将其直接依赖课程加入到它的father集合中，并合并所有这些依赖课程的father集合。最后，根据查询数组，检查每个查询中的课程u是否在课程v的father集合中，以确定是否是先修关系。
时间复杂度:
O(n^2 + q)
空间复杂度:
O(n^2)
代码细节讲解
🦆
在题解中，为什么选择使用深度优先搜索（DFS）而不是广度优先搜索（BFS）来确定课程之间的依赖关系？
▷🦆
题解中提到，对所有入度为0的课程执行DFS。这种方法是否意味着在某些课程的依赖关系为环形的情况下，这些课程将不会被处理？
▷🦆
题解中使用反向边构建图的目的是什么？这样做与正常边构建相比有什么优势或不同之处？
▷🦆
题解中提到通过检查课程u是否在课程v的father集合中来确定是否是先修关系。这种方法在处理大量课程和查询时的性能表现如何？
▷