leetcode

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