1462. 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.

class Solution {
    vector<unordered_set<int>> dp;
    vector<unordered_set<int>> afters;
    unordered_set<int> search(int from) {
        if(!dp[from].empty()) return dp[from];
        unordered_set<int>& cur = dp[from];
        for(auto& nxt : afters[from]) {
            cur.insert(nxt);
            auto res = search(nxt);
            cur.insert(res.begin(), res.end());
        }
        return cur;
    }
    bool isPreReq(int from, int to) {
        if(!dp[from].empty()) return dp[from].count(to);
        return search(from).count(to);
    }
public:
    vector<bool> checkIfPrerequisite(int n, vector<vector<int>>& prerequisites, vector<vector<int>>& queries) {
        dp = vector<unordered_set<int>>(n);
        afters = vector<unordered_set<int>>(n);
        vector<bool> res;
        for(auto& q: prerequisites) {
            afters[q[0]].insert(q[1]);
        }
        for(auto& q: queries) {
            res.push_back(isPreReq(q[0], q[1]));
        }
        return res;
    }
};