Re: [閒聊] 每日leetcode
2872. Maximum Number of K-Divisible Components
## 思路
建Graph, DFS 計算/回傳 節點+子節點總和%k的值
如果加總為0 表示可以分割: res+1
## Code
```python
class Solution:
def maxKDivisibleComponents(self, n: int, edges: List[List[int]], values:
List[int], k: int) -> int:
graph = defaultdict(list)
for a, b in edges:
graph[a].append(b)
graph[b].append(a)
def dfs(node, parent):
nonlocal res
val = values[node]
for child in graph[node]:
if child == parent:
continue
val += dfs(child, node)
val %= k
if val == 0:
res += 1
return val
res = 0
dfs(0, None)
return res
```
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 94.156.205.69 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1734747209.A.BC1.html
討論串 (同標題文章)
完整討論串 (本文為第 1215 之 1554 篇)：