Course Schedule IV LeetCode solution in C++

1
// question similar to find all ancestors of current node
2

3
class Solution {
4
 public:
5
  void dfs(vector<vector<int>> &adj, vector<set<int>> &Anc, int u, int par, vector<int> &vis) {
6
    if (vis[u] != 0) return;
7

8
    vis[u] = 1;
9

10
    for (auto &v : adj[u]) {
11
      if (vis[v] == 0) {
12
        Anc[v].insert(par);
13
        dfs(adj, Anc, v, par, vis);
14
      }
15
    }
16

17
    return;
18
  }
19

20
  vector<bool> checkIfPrerequisite(int numCourses, vector<vector<int>> &prerequisites,
21
                                   vector<vector<int>> &queries) {
22
    int n = numCourses;
23
    vector<vector<int>> adj(n);
24
    vector<set<int>> Anc(n);
25
    vector<bool> ans;
26

27
    for (auto &edge : prerequisites) {
28
      adj[edge[0]].push_back(edge[1]);
29
    }
30

31
    for (int i = 0; i < n; i++) {
32
      vector<int> vis(n, 0);
33
      dfs(adj, Anc, i, i, vis);
34
    }
35

36
    for (auto &EachQuery : queries) {
37
      if (Anc[EachQuery[1]].find(EachQuery[0]) != Anc[EachQuery[1]].end())
38
        ans.push_back(true);
39
      else
40
        ans.push_back(false);
41
    }
42
    return ans;
43
  }
44
};