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
}

大師