leetcode

commit b2245b7df759a72c8aee0739c8167442b1938a22
parent e03b706c90a9c08d7c1af8013ec1d05a937bf3fc
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Sat, 21 Dec 2024 23:12:05 +0100

Daily Problem

Diffstat:
A
Problems/2872.cpp
 | 
49
+++++++++++++++++++++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 50 insertions(+), 0 deletions(-)
diff --git a/Problems/2872.cpp b/Problems/2872.cpp
@@ -0,0 +1,49 @@
+class Solution {
+  public:
+    int maxKDivisibleComponents(int n, const vector<vector<int>> &edges, const vector<int> &values,
+                                int k) const {
+        if (n < 2) return 1;
+
+        vector<long long> lvalues(begin(values), end(values));
+        vector<vector<int>> adj(n);
+        vector<int> count(n);
+
+        for (const auto &e : edges) {
+            adj[e[0]].push_back(e[1]);
+            adj[e[1]].push_back(e[0]);
+
+            count[e[0]]++;
+            count[e[1]]++;
+        }
+
+        queue<int> q;
+        for (int i = 0; i < n; i++) {
+            if (count[i] != 1) continue;
+            q.push(i);
+        }
+
+        int res = 0;
+        while (!q.empty()) {
+            const auto crnt = q.front();
+            q.pop();
+            count[crnt]--;
+
+            long long add = 0;
+            if (lvalues[crnt] % k == 0)
+                res++;
+            else
+                add = lvalues[crnt];
+
+            for (const auto next : adj[crnt]) {
+                if (count[next] == 0) continue;
+
+                lvalues[next] += add;
+                if (--count[next] == 1) {
+                    q.push(next);
+                }
+            }
+        }
+
+        return res;
+    }
+};
diff --git a/README.md b/README.md
@@ -1436,6 +1436,7 @@ reference and a base for solving problems.
 |  2860  |   Medium   | [Happy Students](Problems/2860.cpp)                                                                |
 |  2864  |    Easy    | [Maximum Odd Binary Number](Problems/2864.cpp)                                                     |
 |  2870  |   Medium   | [Minimum Number of Operations to Make Array Empty](Problems/2870.cpp)                              |
+|  2872  |    Hard    | [Maximum Number of K-Divisible Components](Problems/2872.cpp)                                      |
 |  2895  |   Medium   | [Minimum Processing Time](Problems/2895.cpp)                                                       |
 |  2900  |   Medium   | [Longest Unequal Adjacent Groups Subsequence I](Problems/2900.cpp)                                 |
 |  2909  |   Medium   | [Minimum Sum of Mountain Triplets II](Problems/2909.cpp)                                           |