<p>There are a total of <code>numCourses</code> courses you have to take, labeled from <code>0</code> to <code>numCourses - 1</code>. You are given an array <code>prerequisites</code> where <code>prerequisites[i] = [a<sub>i</sub>, b<sub>i</sub>]</code> indicates that you <strong>must</strong> take course <code>a<sub>i</sub></code> first if you want to take course <code>b<sub>i</sub></code>.</p>

<ul>
	<li>For example, the pair <code>[0, 1]</code> indicates that you have to take course <code>0</code> before you can take course <code>1</code>.</li>
</ul>

<p>Prerequisites can also be <strong>indirect</strong>. If course <code>a</code> is a prerequisite of course <code>b</code>, and course <code>b</code> is a prerequisite of course <code>c</code>, then course <code>a</code> is a prerequisite of course <code>c</code>.</p>

<p>You are also given an array <code>queries</code> where <code>queries[j] = [u<sub>j</sub>, v<sub>j</sub>]</code>. For the <code>j<sup>th</sup></code> query, you should answer whether course <code>u<sub>j</sub></code> is a prerequisite of course <code>v<sub>j</sub></code> or not.</p>

<p>Return <i>a boolean array </i><code>answer</code><i>, where </i><code>answer[j]</code><i> is the answer to the </i><code>j<sup>th</sup></code><i> query.</i></p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/05/01/courses4-1-graph.jpg" style="width: 222px; height: 62px;" />
<pre>
<strong>Input:</strong> numCourses = 2, prerequisites = [[1,0]], queries = [[0,1],[1,0]]
<strong>Output:</strong> [false,true]
<strong>Explanation:</strong> 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.
</pre>

<p><strong class="example">Example 2:</strong></p>

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

<p><strong class="example">Example 3:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/05/01/courses4-3-graph.jpg" style="width: 222px; height: 222px;" />
<pre>
<strong>Input:</strong> numCourses = 3, prerequisites = [[1,2],[1,0],[2,0]], queries = [[1,0],[1,2]]
<strong>Output:</strong> [true,true]
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>2 &lt;= numCourses &lt;= 100</code></li>
	<li><code>0 &lt;= prerequisites.length &lt;= (numCourses * (numCourses - 1) / 2)</code></li>
	<li><code>prerequisites[i].length == 2</code></li>
	<li><code>0 &lt;= a<sub>i</sub>, b<sub>i</sub> &lt;= numCourses - 1</code></li>
	<li><code>a<sub>i</sub> != b<sub>i</sub></code></li>
	<li>All the pairs <code>[a<sub>i</sub>, b<sub>i</sub>]</code> are <strong>unique</strong>.</li>
	<li>The prerequisites graph has no cycles.</li>
	<li><code>1 &lt;= queries.length &lt;= 10<sup>4</sup></code></li>
	<li><code>0 &lt;= u<sub>i</sub>, v<sub>i</sub> &lt;= numCourses - 1</code></li>
	<li><code>u<sub>i</sub> != v<sub>i</sub></code></li>
</ul>

class Solution:
    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:
        """
        neetcode solution.
        https://www.youtube.com/watch?v=cEW05ofxhn0
        The prerequisites graph has no cycles.

        E.g., We need to take A first to take B
                B ---> A

        DFS
        For every query, we need to run a DFS.
        For DFS, we may visit all nodes and all edges.
        We do this for q times.
        Time: O(q * (p + n))
        q = # of queries
        p = # of prerequisites (edges)
        n = # of nodes
        
        Can we do better?
        In the above DFS solution, we may visit
        the same edge multiple times for each q.
        Can we cache this? so that we run DFS
        just once. O(p + n)?
        Well... it is actually n * O(p + n).
        n times?
        
        Build a hashmap: 
        course -> hashset of indirect prereq
        A --> hashset of all indirect prerequisites
        B --> hashset of all indirect prerequisites
        ...
        The hashset if bounded by the size n (# of nodes)
        
        Hence, we may run DFS n times.
        (but potentially find already-ran DFS from
        another nodes)

        Time: O(n * (p + n)) + q * O(1)

        p (edges) is upper bounded by n^2.

        [med] 207. Course Schedule
        [med] 210. Course Schedule II
        [hard] 630. Course Schedule III
        """
        from collections import defaultdict

        # build the adj
        adj = defaultdict(list)
        for prereq, crs in prerequisites:
            adj[crs].append(prereq)

        def dfs(crs):
            """
            Build the hashmap.
            {crs: hashset of indirect prereqs}
            """
            if crs not in pre_map:

                # init with the empty hashset
                # = marking as visited.
                pre_map[crs] = set()

                # for all the direct prereq
                # we run the dfs and union 
                # them.
                for prereq in adj[crs]:
                    # union operator |   
                    pre_map[crs] = pre_map[crs] | dfs(prereq)
                
                # also need to add crs
                pre_map[crs].add(crs)       # O(1)

            # base case is here.
            # if crs in pre_map, 
            # we just return the value
            return pre_map[crs]

        # build the prereq map:
        # {crs: hashset of indirect prereqs}
        pre_map = {} 
        for crs in range(numCourses):
            dfs(crs)

        # loop through queries
        # search the prereq hashmap
        res = []
        for u, v in queries:
            # if u prereq of v? 
            # direct or indirect
            res.append(u in pre_map[v])
        return res


    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:
        """
        my solution - accepted @08192024
        Slow..
        """

        def dfs(src, dst):
            nonlocal adj, visited

            # base case 
            if src == dst:
                return True 

            # base case:
            if (src, dst) in memo:
                return memo[(src, dst)]            
            
            # add to the visit 
            visited.add(src)

            for neighbor in adj[src]:
                if neighbor not in visited:
                    if dfs(neighbor, dst):
                        memo[(neighbor, dst)] = True
                        return True

            return False

        adj = {i:[] for i in range(numCourses)}
        for u, v in prerequisites:
            adj[u].append(v)
        
        res = []
        memo = {}
        for src, dst in queries:
            # import pdb; pdb.set_trace()
            visited = set()
            res.append(dfs(src, dst))
        return res
21100