今日题目

https://leetcode.com/problems/course-schedule-iv/description/

思路

本题需要判断一个节点是否是另一个节点的祖先节点。 对此，我们可以为每个节点维护一个集合，存储其所有祖先节点，然后将该集合向下传递给所有子节点。

方法

  • 使用 DFS 遍历所有节点。
  • 为每个节点创建一个集合，并将其传递给子节点。

复杂度

  • 时间复杂度：$O(N^3 + Q)$。每条边最多被访问一次，集合的传递操作为 $O(N)$，因此总时间复杂度为 $O(N^3 + Q)$。

  • 空间复杂度：$O(N^2) + Q$。需要为每个节点存储一个集合，同时还需要存储答案。

代码

class Solution:
    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:
        edges = [[] for _ in range(numCourses)]
        prereq = [set([_]) for _ in range(numCourses)]

        for x, y in prerequisites:
            edges[y].append(x)
        
        def dfs(x):
            for to in edges[x]:
                if len(prereq[to]) == 1:
                    dfs(to)
                prereq[x] = prereq[x] | prereq[to]

        for i in range(numCourses):
            dfs(i)
        
        ans = []
        for x, y in queries:
            if x in prereq[y]:
                ans.append(True)
            else:
                ans.append(False)
        
        return ans