1462.md

1462. Course Schedule IV

Solution 1 (time O(n^3), space O(n^2))

class Solution(object):
    def checkIfPrerequisite(self, numCourses, prerequisites, queries):
        """
        :type numCourses: int
        :type prerequisites: List[List[int]]
        :type queries: List[List[int]]
        :rtype: List[bool]
        """
        g = [[] for _ in range(numCourses)]
        indeg = [0] * numCourses
        ispre = [[False] * numCourses for _ in range(numCourses)]
        for p in prerequisites:
            indeg[p[1]] += 1
            g[p[0]].append(p[1])

        q = deque([i for i in range(numCourses) if indeg[i] == 0])
        while len(q) > 0:
            cur = q.popleft()
            for new in g[cur]:
                ispre[cur][new] = True
                for i in range(numCourses):
                    ispre[i][new] = ispre[i][new] or ispre[i][cur]
                indeg[new] -= 1
                if indeg[new] == 0:
                    q.append(new)
        ans = []
        for q in queries:
            ans.append(ispre[q[0]][q[1]])
        return ans