-
Notifications
You must be signed in to change notification settings - Fork 243
/
2872.cpp
36 lines (33 loc) · 799 Bytes
/
2872.cpp
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
//2872. Maximum Number of K-Divisible Components
//using simple DFS approach
class Solution {
public:
//int res=0;
int dfs(vector<vector<int>>&g,vector<int>& values, int k, int node, int par, int &res)
{
int sum=values[node];
for(int i:g[node])
{
if(i==par)
continue;
int childSum=dfs(g,values,k,i,node,res);
sum+=childSum;
}
if(sum%k==0)
{ ++res;
return 0;
}
return sum;
}
int maxKDivisibleComponents(int n, vector<vector<int>>& edges, vector<int>& values, int k) {
vector<vector<int>>g(n);
for(auto &edge:edges)
{
g[edge[0]].push_back(edge[1]);
g[edge[1]].push_back(edge[0]);
}
int res=0;
dfs(g,values,k,0,-1,res);
return res;
}
};