2872。 K 整除分量的最大數(shù)量

難度：難

主題：樹，深度優(yōu)先搜索

有一個(gè)無向樹，有 n 個(gè)節(jié)點(diǎn)，標(biāo)記為 0 到 n - 1。給定整數(shù) n 和長(zhǎng)度為 n - 1 的二維整數(shù)數(shù)組邊，其中 Edges[i] = [a_i, b_i] 表示節(jié)點(diǎn) a_i 和之間有一條邊b_i 在樹中。

您還會(huì)獲得一個(gè)長(zhǎng)度為 n 的 0 索引 整數(shù)數(shù)組值，其中values[i] 是與第 i^th 節(jié)點(diǎn)關(guān)聯(lián)的值，以及一個(gè)整數(shù) k。

樹的有效分割是通過從樹中刪除任何一組邊（可能是空的）來獲得的，這樣生成的組件都具有可被k整除的值，其中值連接組件 的值是其節(jié)點(diǎn)值的總和。

返回任何有效拆分中組件的最大數(shù)量。

示例1：

• 輸入： n = 5，邊 = [[0,2],[1,2],[1,3],[2,4]]，值 = [1,8,1,4 ,4], k = 6
• 輸出： 2
• 解釋： 我們刪除連接節(jié)點(diǎn) 1 和 2 的邊。生成的分割是有效的，因?yàn)椋?
  • 包含節(jié)點(diǎn) 1 和 3 的組件的值為values[1]values[3] = 12。
  • 包含節(jié)點(diǎn) 0、2、4 的組件的值為values[0]values[2]values[4] = 6。
  • 可以證明，沒有其他有效的分割具有超過 2 個(gè)連通分量。

示例2：

• 輸入： n = 7，邊 = [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6] ]，值 = [3,0,6,1,5,2,1]，k = 3
• 輸出： 3
• 解釋： 我們刪除連接節(jié)點(diǎn) 0 和 2 的邊，以及連接節(jié)點(diǎn) 0 和 1 的邊。由此產(chǎn)生的分割是有效的，因?yàn)椋?
  • 包含節(jié)點(diǎn)0的組件的值為values[0] = 3。
  • 包含節(jié)點(diǎn) 2、5、6 的分量的值為values[2]values[5]values[6] = 9。
  • 包含節(jié)點(diǎn) 1、3、4 的組件的值為values[1]values[3]values[4] = 6。
  • 可以證明，沒有其他有效的分割具有超過 3 個(gè)連通分量。

約束：

• 1 4
• edges.length == n - 1
• 邊[i].length == 2
• 0
• values.length == n
• 0 9
• 1 9
• 值的總和可被 k 整除。
• 生成輸入，使得邊代表有效的樹。

提示：

1. 樹的根位于節(jié)點(diǎn) 0。
2. 如果葉子節(jié)點(diǎn)不能被 k 整除，則它必須與其父節(jié)點(diǎn)在同一組件中，因此我們將其與其父節(jié)點(diǎn)合并。
3. 如果葉節(jié)點(diǎn)可被 k 整除，則它將位于其自己的組件中，因此我們將其與其父節(jié)點(diǎn)分開。
4. 在每一步中，我們要么砍掉一個(gè)葉子節(jié)點(diǎn)，要么合并一個(gè)葉子節(jié)點(diǎn)。樹上的節(jié)點(diǎn)數(shù)減少 1。重復(fù)此過程，直到只剩下一個(gè)節(jié)點(diǎn)。

解決方案：

我們可以實(shí)現(xiàn)深度優(yōu)先搜索（DFS）方法來探索樹，跟蹤組件的值，并找到有效分割的最大數(shù)量。

要點(diǎn)：

• 樹結(jié)構(gòu)：我們正在使用無向樹，其中每個(gè)節(jié)點(diǎn)都有一個(gè)關(guān)聯(lián)的值。我們需要找到通過分裂樹可以獲得的最大連通分量數(shù)，使得每個(gè)分量的值的總和可以被 k 整除。
• DFS 遍歷： 我們使用深度優(yōu)先搜索 (DFS) 來遍歷樹并計(jì)算子樹和。
• 整除性檢查：計(jì)算子樹的和后，如果它能被k整除，則表示該子樹本身可以被視為有效組件。
• 邊移除：通過移除連接子樹和不能被 k 整除的節(jié)點(diǎn)的邊，我們可以最大化有效組件的數(shù)量。

方法：

1. 樹表示： 將邊列表轉(zhuǎn)換為鄰接列表來表示樹。
2. DFS遍歷：從節(jié)點(diǎn)0開始，遞歸計(jì)算每個(gè)子樹中的值的總和。如果總和可被 k 整除，我們可以將該子樹從其父樹中分離出來，從而有效地形成一個(gè)有效的組件。
3. 全局計(jì)數(shù)：維護(hù)一個(gè)全局計(jì)數(shù)器（結(jié)果），跟蹤切割邊緣形成的有效組件的數(shù)量。
4. 最終檢查： 在 DFS 遍歷結(jié)束時(shí)，確保根的子樹總和能被 k 整除，則算作有效分量。

計(jì)劃：

1. 輸入解析： 將輸入轉(zhuǎn)換為可用的形式。具體來說，為樹創(chuàng)建一個(gè)鄰接列表表示。
2. DFS 函數(shù)： 編寫一個(gè)遞歸函數(shù) dfs(node)，計(jì)算以節(jié)點(diǎn)為根的子樹中的值之和。如果該總和可被 k 整除，則增加結(jié)果計(jì)數(shù)器并通過返回 0 來“剪切”邊緣，以防止合并回父級(jí)。
3. 從Root開始DFS：調(diào)用dfs(0)，然后檢查結(jié)果的最終值。

解決步驟：

1. 構(gòu)建樹：將邊列表轉(zhuǎn)換為鄰接列表，以便于遍歷。
2. 初始化訪問數(shù)組：使用訪問數(shù)組來確保我們不會(huì)重新訪問節(jié)點(diǎn)。
3. DFS遍歷：從節(jié)點(diǎn)0開始進(jìn)行DFS。對(duì)于每個(gè)節(jié)點(diǎn)，計(jì)算其子樹的值的總和。
4. 檢查整除性：如果子樹的總和可被 k 整除，則增加結(jié)果并將子樹總和重置為 0。
5. 最終組件檢查： DFS 遍歷之后，檢查整個(gè)樹（以節(jié)點(diǎn) 0 為根）的總和是否可被 k 整除，并在必要時(shí)將其作為單獨(dú)的組件進(jìn)行處理。

讓我們用 PHP 實(shí)現(xiàn)這個(gè)解決方案：2872。 K 可整除分量的最大數(shù)量

<?php
/**
 * @param Integer $n
 * @param Integer[][] $edges
 * @param Integer[] $values
 * @param Integer $k
 * @return Integer
 */
function maxKDivisibleComponents($n, $edges, $values, $k) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * DFS Function
 *
 * @param $graph
 * @param $node
 * @param $parent
 * @param $values
 * @param $k
 * @param $ans
 * @return array|bool|int|int[]|mixed|null
 */
private function dfs($graph, $node, $parent, &$values, $k, &$ans) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example 1
$n = 5;
$edges = [[0,2],[1,2],[1,3],[2,4]];
$values = [1,8,1,4,4];
$k = 6;
echo maxKDivisibleComponents($n, $edges, $values, $k) . "\n"; // Output: 2

// Example 2
$n = 7;
$edges = [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6]];
$values = [3,0,6,1,5,2,1];
$k = 3;
echo maxKDivisibleComponents($n, $edges, $values, $k) . "\n"; // Output: 3
?>

解釋：

1. 樹結(jié)構(gòu)：我們構(gòu)建一個(gè)鄰接表來表示樹結(jié)構(gòu)。每條邊連接兩個(gè)節(jié)點(diǎn)，我們使用這個(gè)鄰接表來遍歷樹。
2. DFS 遍歷： DFS 函數(shù)遞歸計(jì)算以每個(gè)節(jié)點(diǎn)為根的子樹的總和。如果子樹的總和可被 k 整除，我們將結(jié)果遞增并將子樹視為單獨(dú)的有效組件。
3. 返回子樹總和：對(duì)于每個(gè)節(jié)點(diǎn)，DFS 函數(shù)返回其子樹的值的總和。如果子樹可被 k 整除，我們會(huì)通過返回 0 之和來有效地“切割”邊緣，從而防止進(jìn)一步與父節(jié)點(diǎn)合并。
4. 最終檢查： 在 DFS 結(jié)束時(shí)，我們確保如果整棵樹的總和能被 k 整除，則它算作有效組件。

演練示例：

示例1：

輸入：

• n = 5，邊 = [[0,2],[1,2],[1,3],[2,4]]，值 = [1,8,1,4,4]，k = 6。

DFS 從節(jié)點(diǎn) 0 開始：

• 節(jié)點(diǎn) 0：子樹總和 = 1
• 節(jié)點(diǎn) 2：子樹和 = 1 1 4 = 6（可被 6 整除，因此我們可以剪掉這條邊）
• 節(jié)點(diǎn)1：子樹和= 8 4 = 12（能被6整除，剪掉這條邊）
• 最終組件數(shù) = 2。

示例2：

輸入：

• n = 7，邊緣 = [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6]]，值 = [3,0 ,6,1,5,2,1],k = 3.

DFS 從節(jié)點(diǎn) 0 開始：

• 節(jié)點(diǎn) 0：子樹總和 = 3
• 節(jié)點(diǎn)2：子樹和= 6 2 1 = 9（能被3整除，剪掉這條邊）
• 節(jié)點(diǎn) 1：子樹和 = 0 5 = 5（不能被 3 整除，合并這個(gè)和）
• 最終組件數(shù) = 3。

時(shí)間復(fù)雜度：

• DFS 時(shí)間復(fù)雜度： O(n)，其中 n 是節(jié)點(diǎn)數(shù)。我們?cè)L問每個(gè)節(jié)點(diǎn)一次，并在每個(gè)節(jié)點(diǎn)執(zhí)行恒定時(shí)間操作。
• 空間復(fù)雜度： 鄰接表、訪問數(shù)組和遞歸堆棧的 O(n)。

因此，總體時(shí)間和空間復(fù)雜度為 O(n)，使得該方法對(duì)于給定的問題約束非常有效。

聯(lián)系鏈接

如果您發(fā)現(xiàn)本系列有幫助，請(qǐng)考慮在 GitHub 上給 存儲(chǔ)庫(kù) 一個(gè)星號(hào)或在您最喜歡的社交網(wǎng)絡(luò)上分享該帖子？。您的支持對(duì)我來說意義重大！

如果您想要更多類似的有用內(nèi)容，請(qǐng)隨時(shí)關(guān)注我：

• 領(lǐng)英
• GitHub

以上是K 整除組件的最大數(shù)量的詳細(xì)內(nèi)容。更多信息請(qǐng)關(guān)注PHP中文網(wǎng)其他相關(guān)文章！