aboutsummaryrefslogtreecommitdiff
path: root/max_num_k_div_comp.c
blob: c57b9830ef4d0b333ead065dbab084b05d6f4bfc (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
// 2872. Maximum Number of K-Divisible Components
#include "leetcode.h"

/*
 * there is an undirected tree with 'n' nodes labeled from 0 to 'n - 1'. you are
 * given the integer 'n' and a 2d integer array 'edges' of length 'n - 1', where
 * 'edges[i] = [a_i, b_i]' indicates that there is an edge between nodes 'a_i'
 * and 'b_i' in the tree. you are also given a 0-indexed integer array 'values'
 * of length 'n' where 'values[i]' is the value associated with the i'th node
 * and an integer 'k'. a valid split of the tree is obtained by removing any set
 * of edges, possibly empty, from the tree such that the resulting components
 * all have values thatare divisible by 'k', where the value of a connected
 * component is the sum of the values of its node. return the maximum number of
 * components in any valid split
 */

struct vec {
  int *arr;
  int size;
};

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;
}

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);
  }
  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);
  }
  int matches = 0;
  dfs(0, -1, adj, values, k, &matches, n);
  return matches;
}

int main() {
  int e1i[4][2] = {{0, 2}, {1, 2}, {1, 3}, {2, 4}}, v1[] = {1, 8, 1, 4, 4};
  int e2i[6][2] = {{0, 1}, {0, 2}, {1, 3}, {1, 4}, {2, 5}, {2, 6}},
      v2[] = {3, 0, 6, 1, 5, 2, 1};
  struct two_d_arr e1, e2;
  two_d_arr_init(&e1, 4, 2, e1i);
  two_d_arr_init(&e2, 6, 2, e2i);
  printf("%d\n", maxKDivisibleComponents(5, e1.arr, e1.row_size, e1.col_size,
                                         v1, ARRAY_SIZE(v1), 6)); // expect: 2
  printf("%d\n", maxKDivisibleComponents(7, e2.arr, e2.row_size, e2.col_size,
                                         v2, ARRAY_SIZE(v2), 3)); // expect: 2
  two_d_arr_free(&e1);
  two_d_arr_free(&e2);
}