leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

1462.cpp (2904B)

      1 // DFS
      2 class Solution {
      3   public:
      4     vector<bool> checkIfPrerequisite(int numCourses, vector<vector<int>> &prerequisites,
      5                                      vector<vector<int>> &queries) {
      6         vector<vector<int>> adj(numCourses);
      7         vector<unordered_set<int>> pre(numCourses);
      8 
      9         for (auto &p : prerequisites)
     10             adj[p[0]].push_back(p[1]);
     11 
     12         for (int i = 0; i < numCourses; i++) {
     13             unordered_set<int> visited;
     14             stack<int> st;
     15             st.push(i);
     16             visited.insert(i);
     17             while (!st.empty()) {
     18                 int crnt = st.top();
     19                 st.pop();
     20                 for (int &c : adj[crnt]) {
     21                     if (visited.count(c)) continue;
     22                     visited.insert(c);
     23                     pre[c].insert(i);
     24                     st.push(c);
     25                 }
     26             }
     27         }
     28 
     29         vector<bool> res;
     30         for (auto &p : queries)
     31             res.push_back(pre[p[1]].count(p[0]));
     32         return res;
     33     }
     34 };
     35 
     36 // Topological sort with dependency propagation
     37 class Solution {
     38   public:
     39     vector<bool> checkIfPrerequisite(int numCourses, vector<vector<int>> &prerequisites,
     40                                      vector<vector<int>> &queries) {
     41         vector<unordered_set<int>> pre(numCourses);
     42         vector<vector<int>> adj(numCourses);
     43         vector<int> count(numCourses);
     44 
     45         for (auto &p : prerequisites) {
     46             adj[p[0]].push_back(p[1]);
     47             count[p[1]]++;
     48         }
     49 
     50         queue<int> q;
     51         for (int i = 0; i < numCourses; i++)
     52             if (!count[i]) q.push(i);
     53 
     54         while (!q.empty()) {
     55             int crnt = q.front();
     56             q.pop();
     57             for (int &c : adj[crnt]) {
     58                 pre[c].insert(crnt);
     59                 pre[c].insert(pre[crnt].begin(), pre[crnt].end());
     60                 if (!--count[c]) q.push(c);
     61             }
     62         }
     63 
     64         vector<bool> res;
     65         for (auto &p : queries)
     66             res.push_back(pre[p[1]].count(p[0]));
     67         return res;
     68     }
     69 };
     70 
     71 // Topological sort using bitseclass Solution {
     72 public:
     73 vector<bool> checkIfPrerequisite(int numCourses, vector<vector<int>> &prerequisites,
     74                                  vector<vector<int>> &queries) {
     75     vector<bitset<100>> pre(numCourses);
     76     vector<vector<int>> adj(numCourses);
     77     vector<int> count(numCourses);
     78 
     79     for (auto &p : prerequisites) {
     80         adj[p[0]].push_back(p[1]);
     81         count[p[1]]++;
     82     }
     83 
     84     queue<int> q;
     85     for (int i = 0; i < numCourses; i++)
     86         if (!count[i]) q.push(i);
     87 
     88     while (!q.empty()) {
     89         int crnt = q.front();
     90         q.pop();
     91         for (int &c : adj[crnt]) {
     92             pre[c].set(crnt);
     93             pre[c] |= pre[crnt];
     94             if (!--count[c]) q.push(c);
     95         }
     96     }
     97 
     98     vector<bool> res;
     99     for (auto &p : queries)
    100         res.push_back(pre[p[1]][p[0]]);
    101     return res;
    102 }
    103 }
    104 ;