2872. Maximum Number of K-Divisible Components
思路:
纪录每一个点的indegree
先将indegree=1的点(最外围的点)放到queue
如果目前的点cur_node的直可以被k整除
就将ans++
不行的话就把cur_node的值加到跟他连接的那个点
接着把所有跟cur_node连接的点indegree-1
并把indegree=1的点在抓进queue
重复做到queue里没有点
就可以得到答案了
golang code :
func maxKDivisibleComponents(n int, edges [][]int, values []int, k int) int {
var traverse func(currentNode, parentNode int, adjList [][]int,
componentCount *int) int
traverse = func(currentNode, parentNode int, adjList [][]int, componentCount
*int) int {
// Step 1: Initialize sum for the current subtree
sum := 0
// Step 2: Traverse all neighbors
for _, neighborNode := range adjList[currentNode] {
if neighborNode != parentNode {
// Recursive call to process the subtree rooted at the neighbor
sum += traverse(neighborNode, currentNode, adjList, componentCount)
sum %= k // Ensure the sum stays within bounds
}
}
// Step 3: Add the value of the current node to the sum
sum += values[currentNode]
sum %= k
// Step 4: Check if the sum is divisible by k
if sum == 0 {
*componentCount++
}
// Step 5: Return the computed sum for the current subtree
return sum
}
// Step 1: Create adjacency list from edges
adjList := make([][]int, n)
for _, edge := range edges {
node1 := edge[0]
node2 := edge[1]
adjList[node1] = append(adjList[node1], node2)
adjList[node2] = append(adjList[node2], node1)
}
// Step 2: Initialize component count
componentCount := 0 // Use array to pass by reference
// Step 3: Start DFS traversal from node 0
traverse(0, -1, adjList, &componentCount)
// Step 4: Return the total number of components
return componentCount
}

大师