leetcode

commit 5fe64bc7f2fa626f33a1ae2de96a7db8235b8dfd
parent 67e438adf3a29f760c8fac1c3138a66cd134d26e
Author: Jack Sangdahl <jack@pngu.org>
Date:   Thu, 27 Nov 2025 22:21:49 -0700

2872. maximum number of k-divisible components

Diffstat:
M
max_num_k_div_comp.c
 | 
89
+++++++++++++++++++++++++++++++++++++++++++++++++++++--------------------------
M
max_num_k_div_comp.py
 | 
51
++++++++++++++++++++++++---------------------------

2 files changed, 84 insertions(+), 56 deletions(-)
diff --git a/max_num_k_div_comp.c b/max_num_k_div_comp.c
@@ -14,47 +14,78 @@
  * components in any valid split
  */
 
-struct vec {
-  int *arr;
-  int size;
+struct node {
+  int val;
+  struct node *next;
 };
 
-void push(struct vec *a, int val) {
-  a->arr = (int *)realloc(a->arr, (a->size + 1) * sizeof(int));
-  a->arr[a->size] = val;
-  ++a->size;
+struct tree {
+  struct node **adj;
+  int *vals;
+  int n;
+  int ans;
+};
+
+struct node *node_init(int val) {
+  struct node *obj = (struct node *)malloc(sizeof(struct node));
+  obj->val = val;
+  obj->next = NULL;
+  return obj;
+}
+
+void add_edge(struct tree *obj, int u, int v) {
+  struct node *n1 = node_init(v), *n2 = node_init(u);
+  n1->next = obj->adj[u];
+  obj->adj[u] = n1;
+  n2->next = obj->adj[v];
+  obj->adj[v] = n2;
 }
 
-int dfs(int node, int parent, struct vec *adj, int *vals, int k, int *matches,
-        int n) {
-  int sum = 0, neighbour = adj[node].size;
-  for (int i = 0; i < neighbour; ++i) {
-    int n_node = adj[node].arr[i];
-    if (n_node == parent)
-      continue;
-    sum += dfs(n_node, node, adj, vals, k, matches, n);
+long long dfs(int node, int *vals, bool *vis, struct tree *t, int k) {
+  if (vis[node])
+    return 0;
+  vis[node] = true;
+  long long sum = vals[node];
+  struct node *neighbour = t->adj[node];
+  while (neighbour) {
+    sum += dfs(neighbour->val, vals, vis, t, k);
+    neighbour = neighbour->next;
+  }
+  if (!(sum % k)) {
+    t->ans++;
+    return 0;
   }
-  sum += vals[node];
-  sum %= k;
-  if (!sum)
-    ++(*matches);
   return sum;
 }
 
 int maxKDivisibleComponents(int n, int **edges, int edgesSize,
                             int *edgesColSize, int *values, int valuesSize,
                             int k) {
-  struct vec *adj = (struct vec *)malloc(n * sizeof(struct vec));
-  for (int i = 0; i < n; ++i)
-    adj[i] = (struct vec){(int *)malloc(0 * sizeof(int)), 0};
-  for (; edgesSize; ++edges, --edgesSize) {
-    int first = (*edges)[0], second = (*edges)[1];
-    push(adj + first, second);
-    push(adj + second, first);
+  struct tree t;
+  t.n = n;
+  t.vals = values;
+  t.ans = 0;
+  t.adj = (struct node **)malloc(n * sizeof(struct node *));
+  for (int i = 0; i < n; i++)
+    t.adj[i] = NULL;
+  // memset(t.adj, NULL, n * sizeof(struct node));
+  for (int i = 0; i < edgesSize; i++) {
+    int u = edges[i][0], v = edges[i][1];
+    add_edge(&t, u, v);
+  }
+  bool *vis = (bool *)calloc(n, sizeof(bool));
+  dfs(0, values, vis, &t, k);
+  free(vis);
+  for (int i = 0; i < n; i++) {
+    struct node *tmp = t.adj[i];
+    while (tmp) {
+      struct node *del = tmp;
+      tmp = tmp->next;
+      free(del);
+    }
   }
-  int matches = 0;
-  dfs(0, -1, adj, values, k, &matches, n);
-  return matches;
+  free(t.adj);
+  return t.ans;
 }
 
 int main() {
diff --git a/max_num_k_div_comp.py b/max_num_k_div_comp.py
@@ -1,5 +1,4 @@
 # 2872. Maximum Number of K-Divisible Components
-from collections import defaultdict, deque
 
 """
 there is an undirected tree with 'n' nodes labeled from 0 to 'n - 1'. you are
@@ -24,32 +23,30 @@ class Solution(object):
         :type k: int
         :rtype: int
         """
-        if n < 2:
-            return 1
-        graph, degree = defaultdict(list), [0] * n
-        for a, b in edges:
-            graph[a].append(b)
-            graph[b].append(a)
-            degree[a] += 1
-            degree[b] += 1
-        node_values, cnt = values[:], 0
-        leaf = deque([i for i in range(n) if degree[i] == 1])
-        while leaf:
-            curr = leaf.popleft()
-            degree[curr] -= 1
-            carry = 0
-            if node_values[curr] % k == 0:
-                cnt += 1
-            else:
-                carry = node_values[curr]
-            for n in graph[curr]:
-                if degree[n] == 0:
-                    continue
-                degree[n] -= 1
-                node_values[n] += carry
-                if degree[n] == 1:
-                    leaf.append(n)
-        return cnt
+        adj, ans, m = [], 0, len(edges)
+        for i in range(m + 1):
+            adj.append([])
+        for i in range(m):
+            u, v = edges[i][0], edges[i][1]
+            adj[u].append(v)
+            adj[v].append(u)
+        vis = [False for _ in range(n)]
+
+        def dfs(node):
+            nonlocal ans
+            if vis[node]:
+                return 0
+            vis[node] = True
+            s = values[node]
+            for i in adj[node]:
+                s += dfs(i)
+            if s % k == 0:
+                ans += 1
+                return 0
+            return s
+
+        dfs(0)
+        return ans
 
 
 if __name__ == "__main__":