leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

2872.cpp (1223B)

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