leetcode

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

0851.cpp (779B)

      1 class Solution {
      2   public:
      3     vector<int> loudAndRich(vector<vector<int>> &richer, vector<int> &quiet) {
      4         const int n = quiet.size();
      5         vector<vector<int>> adj(n);
      6         vector<int> count(n);
      7         vector<int> res(n);
      8         iota(res.begin(), res.end(), 0);
      9 
     10         for (auto &p : richer) {
     11             adj[p[0]].push_back(p[1]);
     12             count[p[1]]++;
     13         }
     14 
     15         queue<int> q;
     16         for (int i = 0; i < n; i++)
     17             if (!count[i]) q.push(i);
     18 
     19         while (!q.empty()) {
     20             int crnt = q.front();
     21             q.pop();
     22             for (int &c : adj[crnt]) {
     23                 if (quiet[res[c]] > quiet[res[crnt]]) res[c] = res[crnt];
     24                 if (!--count[c]) q.push(c);
     25             }
     26         }
     27         return res;
     28     }
     29 };