Leetcode 1558 Solution

This article provides solution to leetcode question 1558 (course-schedule-iv)
Categories:
Tags:
Access this page by simply typing in "lcs 1558" in your browser address bar if you have bunnylol configured.

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

Solution

class Solution:
    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:
        graph = prerequisites



        child_nodes = collections.defaultdict(set)
        parent_nodes = collections.defaultdict(set)
        nodes = set()



        for src, dst in graph:
            nodes.add(src)
            nodes.add(dst)
            child_nodes[src].add(dst)
            parent_nodes[dst].add(src)



        q = collections.deque()
        for node in nodes:
            if len(parent_nodes[node]) == 0:
                q.append(node)



        ancestors = collections.defaultdict(set)



        while q:
            node = q.popleft()



            for child_node in child_nodes[node]:
                ancestors[child_node] |= ancestors[node] | {node}



                parent_nodes[child_node].remove(node)
                if len(parent_nodes[child_node]) == 0:
                    q.append(child_node)



        ans = []
        for src, dst in queries:
            ans.append(src in ancestors[dst])



        return ans