课程表 IV

难度: Medium

你总共需要上 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]
解释：课程 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 <= n - 1
a_i != b_i
每一对 [a_i, b_i] 都不同
先修课程图中没有环。
1 <= queries.length <= 10⁴
0 <= u_i, v_i <= n - 1
u_i != v_i

Submission

运行时间: 80 ms

内存: 18.9 MB

class Solution:
    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:
        edges = [[] for _ in range(numCourses)]
        indegree = [0] * numCourses
        for u, v in prerequisites:
            edges[v].append(u)  # 反向边
            indegree[u] += 1
        father = [set() for _ in range(numCourses)]
        visited = [False] * numCourses
        def dfs(u):
            if visited[u] == True:
                return 
            visited[u] = True
            for v in edges[u]:
                father[u].add(v)
                dfs(v)
                father[u] |= father[v]
        for u in [i for i in range(numCourses) if indegree[i] == 0]:
            dfs(u)
        n = len(queries)
        ans = [False] * n
        for i in range(n):
            u, v = queries[i]
            if u in father[v]:
                ans[i] = True
        return ans

Explain

该题解使用深度优先搜索（DFS）来确定课程之间的依赖关系。首先，每个课程的入度和一个用于存储每个课程所有先决课程的集合（father）被初始化。题解将先修关系的方向反转，即如果课程u是课程v的先修，则在v到u之间建立一条边。对所有入度为0的课程，也就是没有任何先修要求的课程，执行DFS。在DFS过程中，每访问一个课程，将其直接依赖课程加入到它的father集合中，并合并所有这些依赖课程的father集合。最后，根据查询数组，检查每个查询中的课程u是否在课程v的father集合中，以确定是否是先修关系。

时间复杂度: O(n^2 + q)

空间复杂度: O(n^2)

class Solution:
    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:
        # 创建每个课程的先修课程列表
        edges = [[] for _ in range(numCourses)]
        # 记录每个课程的入度
        indegree = [0] * numCourses
        for u, v in prerequisites:
            edges[v].append(u)  # 为每个课程添加先修课程，反向边
            indegree[u] += 1
        # 初始化每个课程的所有可能的先修课程集合
        father = [set() for _ in range(numCourses)]
        # 记录每个课程是否被访问过，用于DFS
        visited = [False] * numCourses
        # 定义DFS函数，用于更新father集合
        def dfs(u):
            if visited[u] == True:
                return
            visited[u] = True
            for v in edges[u]:
                father[u].add(v)
                dfs(v)
                father[u] |= father[v]
        # 仅对入度为0的课程执行DFS
        for u in [i for i in range(numCourses) if indegree[i] == 0]:
            dfs(u)
        # 处理查询
        n = len(queries)
        ans = [False] * n
        for i in range(n):
            u, v = queries[i]
            if u in father[v]:
                ans[i] = True
        return ans

Explore

在题解中选择使用DFS而不是BFS的主要原因是DFS在这种情况下可以更方便地收集和传播每个节点（课程）的所有依赖关系。使用DFS时，当探索到某一课程的所有依赖课程后，可以在递归回溯过程中方便地将这些依赖信息一并传递回上层节点。这种传播机制在BFS中实现起来较为复杂，因为BFS通常是逐层处理，需要额外的结构来存储和更新每个节点的依赖信息。

题解中提到对所有入度为0的课程执行DFS是基于这些课程没有前置依赖，可以直接开始探索。对于存在环的课程，因为环内各课程的入度都不为0（每个课程至少有一个前置依赖），这些课程不会被初始化启动DFS。然而，这并不意味着这些课程不会被处理；它们将在DFS过程中通过其他入度为0的课程间接触达。如果所有课程都形成一个闭环，则这种方法确实无法处理，因为没有入度为0的课程来启动DFS。

题解中使用反向边构建图是为了便于从任何一个课程开始，能够直接访问到这个课程的所有先修课程，即可以直接追溯到所有可能的先修路径。这种建图方式与常规的先修关系建图（从先修课程指向后续课程的边）相比，使得在确定一个课程的所有可能的先修课程时更为直接和高效，因为可以直接从课程出发，向上追溯所有依赖，而不需要进行额外的查找或反向追踪操作。

这种方法在处理大量课程和查询时的性能主要取决于两个方面：构建每个课程的father集合的效率，以及查询效率。构建集合的时间复杂度主要由图的结构和DFS的效率决定，而每次查询的时间复杂度为O(1)，因为只需检查集合成员关系。然而，如果课程数量非常大，每个课程的father集合可能变得非常大，这将增加内存使用量并可能影响构建集合的时间。在极端情况下，处理大量密集的依赖关系和查询可能导致性能瓶颈，特别是在内存占用和查询响应时间上。