leetcode

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

2872.cpp (1223B)

      1 class Solution {
      2   public:
      3     int maxKDivisibleComponents(int n, const vector<vector<int>> &edges, const vector<int> &values,
      4                                 int k) const {
      5         if (n < 2) return 1;
      6 
      7         vector<long long> lvalues(begin(values), end(values));
      8         vector<vector<int>> adj(n);
      9         vector<int> count(n);
     10 
     11         for (const auto &e : edges) {
     12             adj[e[0]].push_back(e[1]);
     13             adj[e[1]].push_back(e[0]);
     14 
     15             count[e[0]]++;
     16             count[e[1]]++;
     17         }
     18 
     19         queue<int> q;
     20         for (int i = 0; i < n; i++) {
     21             if (count[i] != 1) continue;
     22             q.push(i);
     23         }
     24 
     25         int res = 0;
     26         while (!q.empty()) {
     27             const auto crnt = q.front();
     28             q.pop();
     29             count[crnt]--;
     30 
     31             long long add = 0;
     32             if (lvalues[crnt] % k == 0)
     33                 res++;
     34             else
     35                 add = lvalues[crnt];
     36 
     37             for (const auto next : adj[crnt]) {
     38                 if (count[next] == 0) continue;
     39 
     40                 lvalues[next] += add;
     41                 if (--count[next] == 1) {
     42                     q.push(next);
     43                 }
     44             }
     45         }
     46 
     47         return res;
     48     }
     49 };