NeetCode #618LC-2872HardGraphs
← Back to All Problems#618 · #2872 · Maximum Number of K-Divisible Components(可以被 K 整除连通块的最大数目)
📌 Problem Statement & Constraints
You are given a tree of
n nodes, edges, values for each node, and an integer k. Remove some edges so that every resulting component has a sum divisible by k. Return the maximum number of components. Constraints: 1 <= n <= 3 * 10^4, 1 <= k <= 10^9, 1 <= values[i] <= 10^9; the total sum is divisible by k.💡 Core Algorithmic Approaches
- A post-order DFS: for each node, compute the sum of its component (its value plus the un-cut children's sums).
- If that sum is divisible by
k, cut the edge to the parent -- this component is complete, and the parent receives 0. - Cutting greedily bottom-up is optimal: a subtree that can be cut should be cut as early as possible.
- The total sum being divisible by
kguarantees the root's remainder is also divisible, so all components are valid.
💻 Benchmark Python3 Implementation
class Solution:
def maxKDivisibleComponents(self, n: int, edges: List[List[int]], values: List[int], k: int) -> int:
from collections import defaultdict
g = defaultdict(list)
for a, b in edges:
g[a].append(b)
g[b].append(a)
self.count = 0
def dfs(node: int, parent: int) -> int:
total = values[node]
for nxt in g[node]:
if nxt == parent:
continue
total += dfs(nxt, node) # gather the un-cut children
if total % k == 0: # this component is complete
self.count += 1
return 0 # the parent receives nothing
return total # the remainder flows upward
dfs(0, -1)
return self.count⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): one post-order traversal.
💾 Space Complexity
O(n) for the adjacency list and the recursion depth.
⚠️ Interview Pitfalls & Follow-ups
- Counting only the root component: every cut creates a component, and the root's component is counted when its total is divisible.
- Returning the total instead of 0 after a cut: the parent would double-count the cut-off sum.
- Trying to enumerate all edge subsets: exponential.
- Forgetting the
parentguard: the DFS would loop on the undirected tree.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.