What pattern does Course Schedule IV follow?

It follows a graph indegree plus topological ordering pattern, where building a reachability matrix lets us answer all queries efficiently.

Can DFS alone solve Course Schedule IV?

DFS can identify reachability but may be inefficient per query; topological ordering with an isReachable matrix handles multiple queries faster.

Why do we need a reachability matrix?

It precomputes direct and indirect prerequisites so each query can be answered in constant time, avoiding repeated graph traversal.

What are the main pitfalls in solving Course Schedule IV?

Common mistakes include ignoring indirect prerequisites, running DFS per query, and incorrectly updating reachability during topological processing.

How do topological sort and indegree tracking help here?

They ensure courses are processed in prerequisite order, propagating reachability correctly and efficiently without revisiting nodes unnecessarily.

#1462

Medium

auto_awesome图·搜索

LeetCode 题解工作台

课程表 IV

你总共需要上 numCourses 门课，课程编号依次为 0 到 numCourses-1 。你会得到一个数组 prerequisite ，其中 prerequisites[i] = [a i , b i ] 表示如果你想选 b i 课程，你必须先选 a i 课程。有的课会有直接的先修课程，比…

深度优先搜索广度优先搜索图拓扑排序

题目描述

你总共需要上 numCourses 门课，课程编号依次为 0 到 numCourses-1 。你会得到一个数组 prerequisite ，其中 prerequisites[i] = [a_i, b_i] 表示如果你想选 b_i 课程，你必须先选 a_i 课程。

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

先决条件也可以是间接的。如果课程 a 是课程 b 的先决条件，课程 b 是课程 c 的先决条件，那么课程 a 就是课程 c 的先决条件。

你也得到一个数组 queries ，其中 queries[j] = [u_j, v_j]。对于第 j 个查询，您应该回答课程 u_j 是否是课程 v_j 的先决条件。

返回一个布尔数组 answer ，其中 answer[j] 是第 j 个查询的答案。

示例 1：

输入：numCourses = 2, prerequisites = [[1,0]], queries = [[0,1],[1,0]]
输出：[false,true]
解释：[1, 0] 数对表示在你上课程 0 之前必须先上课程 1。
课程 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 <= 100
0 <= prerequisites.length <= (numCourses * (numCourses - 1) / 2)
prerequisites[i].length == 2
0 <= a_i, b_i <= numCourses - 1
a_i != b_i
每一对 [a_i, b_i] 都不同
先修课程图中没有环。
1 <= queries.length <= 10⁴
0 <= u_i, v_i <= numCourses - 1
u_i != v_i

lightbulb

解题思路

方法一：Floyd 算法

我们创建一个二维数组 $f$ ，其中 $f[i][j]$ 表示节点 $i$ 到节点 $j$ 是否可达。

接下来，我们遍历先修课程数组 $prerequisites$ ，对于其中的每一项 $[a, b]$ ，我们将 $f[a][b]$ 设为 $true$ 。

然后，我们使用 Floyd 算法计算出所有节点对之间的可达性。

具体地，我们使用三重循环，首先枚举中间点 $k$ ，接下来枚举起点 $i$ ，最后枚举终点 $j$ 。对于每一次循环，如果节点 $i$ 到节点 $k$ 可达，且节点 $k$ 到节点 $j$ 可达，那么节点 $i$ 到节点 $j$ 也是可达的，我们将 $f[i][j]$ 设为 $true$ 。

在计算完所有节点对之间的可达性之后，对于每一个查询 $[a, b]$ ，我们直接返回 $f[a][b]$ 即可。

时间复杂度 $O(n^3)$ ，空间复杂度 $O(n^2)$ 。其中 $n$ 为节点数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def checkIfPrerequisite(
        self, n: int, prerequisites: List[List[int]], queries: List[List[int]]
    ) -> List[bool]:
        f = [[False] * n for _ in range(n)]
        for a, b in prerequisites:
            f[a][b] = True
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    if f[i][k] and f[k][j]:
                        f[i][j] = True
        return [f[a][b] for a, b in queries]

speed

复杂度分析

指标	值
时间	complexity is O(N^3 + Q) because building the reachability matrix involves O(N^3) operations for N courses, and answering Q queries is O(Q). Space complexity is O(N^2) to store the reachability matrix.
空间	O(N^2)

psychology

面试官常问的追问

外企场景

question_mark
Are you considering both direct and indirect prerequisites?
question_mark
Can you optimize repeated queries without running DFS each time?
question_mark
How does topological ordering simplify the prerequisite propagation?

warning

常见陷阱

外企场景

error
Ignoring indirect prerequisites leads to incorrect query answers.
error
Attempting DFS/BFS per query may exceed time limits on large inputs.
error
Failing to initialize or update the reachability matrix correctly during topological processing.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Check if all courses can be completed given the same prerequisites graph.
arrow_right_alt
Determine the minimum number of courses required to satisfy a set of query constraints.
arrow_right_alt
Compute the longest chain of prerequisites instead of answering individual queries.

help

常见问题

外企场景

继续练习

#1203 项目管理 #802 找到最终的安全状态 #2328 网格图中递增路径的数目