<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]:
        #27/8/24
        def dfs(crs):
            if crs in hashMap:
                return hashMap[crs]
            
            for pre in adj[crs]:
                hashMap[crs] |= dfs(pre)
            hashMap[crs].add(crs)
            return hashMap[crs]


        adj = defaultdict(list)

        for pre,crs in prerequisites:
            adj[crs].append(pre)

        hashMap = defaultdict(set)
        
        for crs in range(numCourses):
            dfs(crs)

        res = []
        for pre, crs in queries:
            if pre in hashMap[crs]:
                res.append(True)
            else:
                res.append(False)
        return res
        


        #20/8/24

        def dfs(crs):
            if crs in hashMap:
                return hashMap[crs]
            
            for pre in adj[crs]:
                hashMap[crs] |= dfs(pre)
            hashMap[crs].add(crs)
            return hashMap[crs]


        adj = defaultdict(list)

        for pre,crs in prerequisites:
            adj[crs].append(pre)

        hashMap = defaultdict(set)


        for crs in range(numCourses):
            dfs(crs)
        
        res = []
        for pre, crs in queries:
            res.append(pre in hashMap[crs])
        return res





















        # 6/8/24

        adj = defaultdict(list)

        for pre, crs in prerequisites:
            adj[crs].append(pre)

        def dfs(crs):
            if crs in cache:
                return cache[crs]

            for pre in adj[crs]:
                cache[crs] |= dfs(pre)
            cache[crs].add(crs)
            return cache[crs]

        cache = defaultdict(set)
        for n in range(numCourses):
            dfs(n)

        res = []
        for pre,crs in queries:
            if pre in cache[crs]:
                res.append(True)
            else:
                res.append(False)

        return res


























        #23/7/24

        #since we need to collate the direct and indirect prerequisites, lets store it like this crs ->[indirect, direct pre req]

        adj = defaultdict(list)

        for pre,crs in prerequisites:
            adj[crs].append(pre)

        def dfs(crs):
            if crs in hashMap:
                return hashMap[crs]

            for pre in adj[crs]:
                hashMap[crs] |= dfs(pre)

            hashMap[crs].add(crs) # this is so that if other crs need this as prereq they will be added as well, cos we will add hashMap[crs] and if we dont add crs hashMap[crs] wont contain crs, so only contain the indirect prereq and not the direct prereq
            return hashMap[crs]



        hashMap = defaultdict(set)

        for crs in range(numCourses):
            dfs(crs)

        res = []
        for pre, crs in queries:
            if pre in hashMap[crs]:
                res.append(True)
            else:
                res.append(False)

        return res  

        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        # 9/4/24
        adj = defaultdict(list)
        for pre, crs in prerequisites:
            adj[crs].append(pre)

        hashMap = defaultdict(set)
        visit = set()

        def dfs(crs):
            if crs in hashMap:
                return hashMap[crs]

            for pre in adj[crs]:
                hashMap[crs] |= dfs(pre)

            hashMap[crs].add(crs)
            return hashMap[crs]

            

            


        for crs in range(numCourses):
            dfs(crs)

        res = []

        for pre, crs in queries:
            if pre in hashMap[crs]:
                res.append(True)
            else:
                res.append(False)

        return res

        





























        #21/3/24
        # idea is to set up a hashmap of crs : [prerequisites] #instead of using list use set makes more sense


        adj = defaultdict(list)
        
        for pre, crs in prerequisites:
            adj[crs].append(pre)

        def dfs(crs):
            if crs in hashMap:
                return hashMap[crs]

            for pre in adj[crs]:
                hashMap[crs] |= dfs(pre)

            hashMap[crs].add(crs)
            return hashMap[crs] 

        hashMap = defaultdict(set)

        for crs in range(numCourses):
            dfs(crs)


        res = []
        for pre, crs in queries:
            if pre in hashMap[crs]:
                res.append(True)
            else:
                res.append(False)

        return res






















        #10/2/24

        adj = {i:[] for i in range(numCourses)}

        for pre, crs in prerequisites:
            adj[crs].append(pre)

        #cos now we need to get the indirect prerequisites, so in the dfs i will do, i will have to return all the prereq

        def dfs(crs):
            if crs in hashMap:
                return hashMap[crs]

            for pre in adj[crs]:
                hashMap[crs] |= dfs(pre)

            hashMap[crs].add(crs)
            return hashMap[crs]



        hashMap = defaultdict(set)
        for crs in range(numCourses):
            dfs(crs)

    












































        adj = {i:[] for i in range(numCourses)}

        for pre, crs in prerequisites:
            adj[crs].append(pre)

        
        hashmap = defaultdict(set)

        def dfs(crs):
            if crs in hashmap:
                return hashmap[crs]

            for pre in adj[crs]:
                hashmap[crs] |= dfs(pre)
            
            hashmap[crs].add(crs)
            return hashmap[crs]



        for crs in range(numCourses):
            dfs(crs)

        print(hashmap)
        res = []
        for pre, crs in queries:
            if pre in hashmap[crs]:
                res.append(True)
            else:
                res.append(False)

        return res

























        #3/10/23
        adj = {i:[] for i in range(numCourses)}

        for pre, crs in prerequisites:
            adj[crs].append(pre)

        def dfs(crs):
            if crs in hashmap:
                return hashmap[crs]

            for pre in adj[crs]:
                hashmap[crs] |= dfs(pre)
            hashmap[crs].add(crs)
            return hashmap[crs]


        hashmap = defaultdict(set)
        for crs in range(numCourses):
            dfs(crs)

        print(hashmap)
        
        res = []
        for pre, crs in queries:
            if pre in hashmap[crs]:
                res.append(True)
            else:
                res.append(False)

        return res






























        #1/10/23

        adj = defaultdict(list)

        for pre, crs in prerequisites:
            adj[crs].append(pre)

        def dfs(crs):
            if crs in hashmap:
                return hashmap[crs]

            for pre in adj[crs]:
                hashmap[crs] |= dfs(pre)
            hashmap[crs].add(crs)
            return hashmap[crs]




        hashmap = defaultdict(set)
        # no need for visit as no cycles as stated in question
        for crs in range(numCourses):
            dfs(crs)

        res = []
        for pre, crs in queries:
            if pre in hashmap[crs]:
                res.append(True)
            else:
                res.append(False)
        return res











































        #can use union find?? cannot cos for undirected graphs only!!!!!
        #idea for this question is iterate through the adj list, in topological order, then we store all the children in a hashmap[crs] = set(children, grandchildren etc........)
        # we do so as if we dont enter the for loop, we add hashmap[crs].add(crs), and return this to its parent 
        #if we enter for loop, hashmap[crs] will be equals hashmap[crs] | dfs(pre), and this is possible because its a set
        #then we will return our hashmap[crs] to parent, and not forgetting to add themselves to its prereq, so that prarent will have its children, and itself as a prereq
        adj = defaultdict(list)

        for pre, crs in prerequisites:
            adj[crs].append(pre)

        def dfs(crs):
            if crs in hashmap:
                return hashmap[crs]

            for pre in adj[crs]:
                hashmap[crs] |= dfs(pre)

            hashmap[crs].add(crs)
            return hashmap[crs]



        hashmap = defaultdict(set)
        #question say no cycles thus we dont need the visit set
        for crs in range(numCourses):
            dfs(crs)

        res = []
        for pre, crs in queries:
            if pre in hashmap[crs]:
                res.append(True)
            else:
                res.append(False)

        return res

































































        #9/9/23
        adj = defaultdict(list)

        for pre, crs in prerequisites:
            adj[crs].append(pre)
        
        def dfs(crs):
            if crs not in hashMap:
                hashMap[crs] = set()
                
                for pre in adj[crs]:
                    hashMap[crs] |= dfs(pre)
                hashMap[crs].add(crs) # if we dont have this, at the end of a graph, nothing will get added to the hashap[crs], and we wont be returning anything, hashmap[crs] will all be empty sets

            return hashMap[crs]
            
        
        hashMap = {}
        for crs in range(numCourses):
            dfs(crs)


        res = []
        print(hashMap)
        for pre, crs in queries:
            if pre in hashMap[crs]:
                res.append(True)
            else:
                res.append(False)
        return res



        #9/9/23 # me trying with time complexity of O(Q*(V+E)) (time limit exceeded for large inputs)
        # adj = defaultdict(list)

        # for pre, crs in prerequisites:
        #     adj[crs].append(pre)
        
        # def dfs(crs):
        #     if crs == target:
        #         return True

        #     if adj[crs] == []: # means we reach the end of the graph and could not find target
        #         return False 

        #     for pre in adj[crs]:
        #         if dfs(pre):
        #             return True

        #     return False
            
        
        # res = []
        # for pre, crs in queries:
        #     target = pre
        #     if dfs(crs):
        #         res.append(True)
        #     else:
        #         res.append(False)
        # return res
            



        




































        #4/9/23 (saw neetcode ans, so his idea is to do the normal dfs, but append a prereq list, and then we loop through the queries and cross check on that list)

        adj = defaultdict(list) # using this if the ke
        
        for pre, crs in prerequisites:
            adj[crs].append(pre)

        def dfs(crs):
            if crs not in prereqMap:
                prereqMap[crs] = set()
                for nei in adj[crs]:
                    prereqMap[crs] |= dfs(nei) # this is like union for the set
                prereqMap[crs].add(crs) # need this line cos we need to add the current course as a prereq as well, dont understand draw out the graph and trace it very important
            return prereqMap[crs]

        prereqMap = {}
        for crs in range(numCourses):
            dfs(crs)

        print(prereqMap)

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

        

        
20900