LC 1462. Course Schedule (ACTUAL PREREQUSITES IN TOPO ARRAY) V.IMPORTANT

class Solution {
public:

    vector<unordered_set<int> > kahn(int numCourses, vector<vector<int> > &prerequisites){
        vector<vector<int> > adj(numCourses, vector<int>());
        vector<int> indegree(numCourses, 0);
        queue<int> q;
        //reachable[u] = {a, b, c} => u can be reached from Node a, b & c.
        // Node a, b & c are the ACTUAL and ALL the prerequisites that node u has.
        //All these nodes will appear on the left side of Node u in topo order array.
        // All the nodes to left of 'u', ONLY A SUBSET OF THEM CAN ACTUALLY REACH u (those who can reach u , are the prerequisites of u).
        //It is actually the lemma where we state: All the nodes to right of X in topo order, are not reachable from u, only some subset of them is actually reachable.(THIS IS WHAT HAPPENS WHILE WE DO THE RELAXATION STEP during the problem of finding shortest path in weighted DAG).
        //A node X can update only a subset of nodes present to the right of topo order array while we traverse the topo order to relax edges
        //Traversing topo order means, if we reach a NODE following the topo order, all the paths that could reach the NODE have been considered(indegree[NODE] == 0), and out of all the path, we keep the path with minimum weight.(the relaxation step that we follow till we reach that node). All the Nodes after NODE in topo order can't reach NODE as per lemma 1 (node X can't reach to any node on the left of it), so their incomplete computation of min distance won't affect the process of finding the minimum weighted path to NODE from a source, as they can't reach NODE anyway(there is no path from those nodes to NODE, which means there is no edge that ORIGINATE from those node and are a part of the path that reaches NODE that should have considered)
        vector<unordered_set<int> > reachable(numCourses);

        //build adjacency list & compute indegree
        for(int i = 0; i < prerequisites.size(); i++){
            int u = prerequisites[i][0], v = prerequisites[i][1];
            adj[u].push_back(v);
            indegree[v]++;
        }

        //find indegree = 0 node to start kahn algorithm
        for(int i = 0; i < indegree.size(); i++){
            if(indegree[i] == 0){
                //indegree[node] = 0, means ALL the paths that could have reached node are already considered.
                //But as these are the initial node with indegree = 0, there are no nodes that could reach these
                q.push(i);
            }
        }

        while(!q.empty()){
            int front = q.front();
            q.pop();

            for(int i = 0; i < adj[front].size(); i++){
                //IMPORTANT
                //child is reachable from front (front -> child)
                //reachable[child] = front + reachable[front]
                //ALL those nodes which could reach front + front node itself, could also reach the child.
                //ALL those nodes which are the prerequisites of front node + front node itself, are the prerequisites of child node as well (trasitive closure property)
                int child = adj[front][i];

                //reachable[child] = front node + reachable[front]
                reachable[child].insert(front);

                for(int node : reachable[front]){
                    reachable[child].insert(node);
                }

                indegree[child]--;

                if(indegree[child] == 0){
                    q.push(child);
                }

            }
        }
        return reachable;
    }

    vector<bool> checkIfPrerequisite(int numCourses, vector<vector<int>>& prerequisites, vector<vector<int>>& queries) {
        //reachable[i] stores the SUBSET of the nodes that are present on the left of node 'i' in topo order array which can ACTUALLY REACH node 'i', meaning these nodes have a direct / indirect path from themselves to node 'i'.
        //IMPORTANT - THIS SUBSET CONTAINS THE NODES THAT ARE THE ACTUAL PREREQUISITES OF NODE 'i'.
        vector<unordered_set<int> > reachable = kahn(numCourses, prerequisites);

        vector<bool> res(queries.size(), false);
        for(int q = 0; q < queries.size(); q++){
            int u = queries[q][0], v = queries[q][1];

            //return true if u->v meaning (u is a prerequisite of v)
            bool prerequisite = false;
            for(int i : reachable[v]){
                if(i == u){
                    prerequisite = true;
                }
            }
            res[q] = prerequisite;
        }
        return res;
    }
};