1462_课程表IV

难度：中等

题目

你总共需要上 n 门课，课程编号依次为 0 到 n-1 。

有的课会有直接的先修课程，比如如果想上课程 0 ，你必须先上课程 1 ，那么会以 [1,0] 数对的形式给出先修课程数对。

给你课程总数 n 和一个直接先修课程数对列表 prerequisite 和一个查询对列表 queries 。

对于每个查询对 queries[i] ，请判断 queries[i][0] 是否是 queries[i][1] 的先修课程。

请返回一个布尔值列表，列表中每个元素依次分别对应 queries 每个查询对的判断结果。

注意：如果课程 a 是课程 b 的先修课程且课程 b 是课程 c 的先修课程，那么课程 a 也是课程 c 的先修课程。

示例

示例一：

输入：n = 2, prerequisites = [[1,0]], queries = [[0,1],[1,0]]
输出：[false,true]
解释：课程 0 不是课程 1 的先修课程，但课程 1 是课程 0 的先修课程。

示例二：

输入：n = 2, prerequisites = [], queries = [[1,0],[0,1]]
输出：[false,false]
解释：没有先修课程对，所以每门课程之间是独立的。

示例三：

img

输入：n = 3, prerequisites = [[1,2],[1,0],[2,0]], queries = [[1,0],[1,2]]
输出：[true,true]

示例四：

输入：n = 3, prerequisites = [[1,0],[2,0]], queries = [[0,1],[2,0]]
输出：[false,true]

示例五：

输入：n = 5, prerequisites = [[0,1],[1,2],[2,3],[3,4]], queries = [[0,4],[4,0],[1,3],[3,0]]
输出：[true,false,true,false]

提示

  • $2 <= n <= 100$
  • $0 <= prerequisite.length <= (n * (n - 1) / 2)$
  • $0 <= prerequisite[i][0], prerequisite[i][1] < n$
  • $prerequisite[i][0] != prerequisite[i][1]$
  • 先修课程图中没有环。
  • 先修课程图中没有重复的边。
  • $1 <= queries.length <= 10^4$
  • $queries[i][0] != queries[i][1]$

解题

用 floyd 算法构建连接图，刷新每个中转点的入度点和出度点的连通性

1
2
3
4
5
6
7
8
9
10
11
12
boolean[][] isConnected = new boolean[numCourses][numCourses];
for (int[] pre:prerequisites){
  isConnected[pre[0]][pre[1]] = true;
}
for (int m = 0; m<numCourses; m++){ // 中间节点
  for (int s = 0; s<numCourses; s++){ // 开始节点
    for (int e = 0; e<numCourses; e++) { //结束节点
      if (isConnected[s][e]) continue;
      if (isConnected[s][m] && isConnected[m][e]) isConnected[s][e] = true;
    }
  }
}

然后遍历查询数组，输出结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public List<Boolean> checkIfPrerequisite(int numCourses, int[][] prerequisites, int[][] queries){
  boolean[][] isConnected = new boolean[numCourses][numCourses];
  for (int[] pre:prerequisites){
    isConnected[pre[0]][pre[1]] = true;
  }
  for (int m = 0; m<numCourses; m++){ // 中间节点
    for (int s = 0; s<numCourses; s++){ // 开始节点
      for (int e = 0; e<numCourses; e++) { //结束节点
        if (isConnected[s][e]) continue;
        if (isConnected[s][m] && isConnected[m][e]) isConnected[s][e] = true;
      }
    }
  }
  List<Boolean> ans = new ArrayList<>();
  for (int[] query:queries){
    ans.add(isConnected[query[0]][query[1]]);
  }
  return ans;
}