[link](https://leetcode.com/problems/course-schedule-iv/)

---

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course ai first if you want to take course bi.

For example, the pair [0, 1] indicates that you have to take course 0 before you can take course 1.
Prerequisites can also be indirect. If course a is a prerequisite of course b, and course b is a prerequisite of course c, then course a is a prerequisite of course c.

You are also given an array queries where queries[j] = [uj, vj]. For the jth query, you should answer whether course uj is a prerequisite of course vj or not.

Return a boolean array answer, where answer[j] is the answer to the jth query.

#### Example 1:

Input: numCourses = 2, prerequisites = [[1,0]], queries = [[0,1],[1,0]]
Output: [false,true]
Explanation: The pair [1, 0] indicates that you have to take course 1 before you can take course 0.
Course 0 is not a prerequisite of course 1, but the opposite is true.

Example 2:

Input: numCourses = 2, prerequisites = [], queries = [[1,0],[0,1]]
Output: [false,false]
Explanation: There are no prerequisites, and each course is independent.

Example 3:

Input: numCourses = 3, prerequisites = [[1,2],[1,0],[2,0]], queries = [[1,0],[1,2]]
Output: [true,true]

#### Constraints:

- 2 <= numCourses <= 100
- 0 <= prerequisites.length <= (numCourses * (numCourses - 1) / 2)
- prerequisites[i].length == 2
- 0 <= ai, bi <= n - 1
- ai != bi
- All the pairs [ai, bi] are unique.
- The prerequisites graph has no cycles.
- 1 <= queries.length <= 104
- 0 <= ui, vi <= n - 1
- ui != vi

---

The adj dictionary serves as the adjacency list of the courses, similar to previous implementations. For each prerequisite pair (pre, crs) in prerequisites, the code adds pre as a neighbor of crs.

The preMap dictionary is used to store the prerequisites of each course. It maps a course to a set of its prerequisites. The dfs function populates this preMap dictionary using a depth-first search traversal. For each course crs, if its prerequisites are not already computed and stored in preMap, the function computes them by recursively traversing the prerequisites of crs and adding them to the set. The crs itself is also added to the set.

The outer loop iterates through all the courses (numCourses) and calls the dfs function for each course to populate the preMap dictionary.

The res list will store the boolean results for each query. The second loop iterates through each query (u, v) in the queries list. For each query, it checks if course u is in the set of prerequisites for course v (i.e., u is a subset of preMap[v]). If so, it appends True to the res list; otherwise, it appends False. Finally, the res list containing the results of the queries is returned.

#### Solution 1

class Solution:
    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:
        adj = { i : [] for i in range(numCourses) }
        for pre, crs in prerequisites:
            adj[crs].append(pre)

        preMap = {}
        def dfs(crs):
            if crs not in preMap:
                preMap[crs] = set()
                for pre in adj[crs]:
                    preMap[crs] |= dfs(pre)
                preMap[crs].add(crs)
            return preMap[crs]
                    
        for crs in range(numCourses):
            dfs(crs)

        res = []
        for u, v in queries:
            res.append(u in preMap[v])

        return res    

O(T): O(V + E + Q)
O(S): O(V + E)