Course Schedule IV LeetCode solution in Python

1
class Solution:
2
    """
3
    one approach I can think of is, given a graph,
4
    the query[a, b] will be true if there exists a path from a to b in the graph
5
    else a will not be a prerequisite of b
6
    but this approach may not scale as the # of queries will increase
7
    """
8

9
    def checkIfPrerequisite(
10
        self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]
11
    ) -> List[bool]:
12
        graph = {node: set() for node in range(numCourses)}
13
        for pre in prerequisites:
14
            graph[pre[0]].add(pre[1])
15

16
        def path(cur_node, node_b):
17
            if cur_node == node_b:
18
                return True
19
            for neighbor in graph[cur_node]:
20
                if path(neighbor, node_b):
21
                    return True
22
            return False
23

24
        ans = []
25
        for query in queries:
26
            # see if there is a path from query[0] to query[1]
27
            ans.append(path(query[0], query[1]))
28
        return ans