K で割り切れる成分の最大数-PHPチュートリアル-php.cn

2872。 K で割り切れる成分の最大数

難易度: 難しい

トピック: ツリー、深さ優先検索

0 から n - 1 までのラベルが付けられた n 個のノードを持つ無向ツリーがあります。整数 n と lengthn - 1 の 2D 整数配列エッジが与えられます。ここで、edges[i] = [a_i, b_i] は、ノード a_i とノードの間にエッジがあることを示します。 b_i がツリーにいます。

長さ n の 0 インデックス付き 整数配列値も与えられます。ここで、values[i] は i^番目ノードに関連付けられた値、および整数 k です。

ツリーの有効な分割は、結果として得られるコンポーネントがすべて k で割り切れる値を持つように、ツリーから任意のエッジのセット (空の可能性があります) を削除することによって取得されます。ここで、 の値接続コンポーネントのノードの値の合計です。

有効な分割内のコンポーネントの最大数を返します。

例 1:

Maximum Number of K-Divisible Components

入力: n = 5、エッジ = [[0,2],[1,2],[1,3],[2,4]]、値 = [1,8,1,4 ,4]、k = 6
出力: 2
説明: ノード 1 と 2 を接続するエッジを削除します。結果の分割は次の理由から有効です。
- ノード 1 と 3 を含むコンポーネントの値は、values[1] value[3] = 12 です。
- ノード 0、2、および 4 を含むコンポーネントの値は、values[0]、values[2]、values[4] = 6 です。
- 他の有効な分割には 2 つを超える連結成分がないことがわかります。

例 2:

Maximum Number of K-Divisible Components

入力: n = 7、エッジ = [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6] ]、値 = [3,0,6,1,5,2,1]、k = 3
出力: 3
説明: ノード 0 を 2 に接続するエッジと、ノード 0 を 1 に接続するエッジを削除します。結果の分割は次の理由から有効です。
- ノード 0 を含むコンポーネントの値は、values[0] = 3 です。
- ノード 2、5、6 を含むコンポーネントの値は、values[2]、values[5]、values[6] = 9 です。
- ノード 1、3、4 を含むコンポーネントの値は、values[1]、values[3]、values[4] = 6 です。
- 他の有効な分割には 3 つを超える連結成分がないことがわかります。

制約:

1 4
edges.length == n - 1
edges[i].length == 2
0 n
^{0 9}
^{1 9}

ヒント:

解決策:

深さ優先検索 (DFS) アプローチを実装して、ツリーを探索し、コンポーネントの値を追跡し、有効な分割の最大数を見つけることができます。

重要なポイント:

ツリー構造: 各ノードが関連する値を持つ無向ツリーを操作しています。各コンポーネントの値の合計が k で割り切れるようにツリーを分割することで取得できる接続コンポーネントの最大数を見つける必要があります。
DFS トラバーサル: 深さ優先検索 (DFS) を使用してツリーをトラバースし、サブツリーの合計を計算します。
割り算チェック: サブツリーの合計を計算した後、それが k で割り切れる場合、そのサブツリーはそれ自体で有効なコンポーネントとみなせることを意味します。
エッジの削除: サブツリーの合計が k で割り切れないノードを接続するエッジを削除することで、有効なコンポーネントの数を最大化できます。

アプローチ：

ツリー表現: エッジリストを隣接リストに変換してツリーを表現します。
DFS Traversal: ノード 0 から開始して、各サブツリーの値の合計を再帰的に計算します。合計が k で割り切れる場合、そのサブツリーを親から切り離し、有効なコンポーネントを効果的に形成できます。
グローバルカウント: 刃先によって形成された有効なコンポーネントの数を追跡するグローバルカウンタ (結果) を維持します。
最終チェック: DFS トラバーサルの最後に、ルートのサブツリーの合計が k で割り切れる場合、有効なコンポーネントとしてカウントされることを確認します。

プラン：

入力解析: 入力を使用可能な形式に変換します。具体的には、ツリーの隣接リスト表現を作成します。
DFS 関数: ノードをルートとするサブツリー内の値の合計を計算する再帰関数 dfs(node) を作成します。この合計が k で割り切れる場合は、結果カウンターをインクリメントし、親にマージして戻らないように 0 を返してエッジを「カット」します。
ルートから DFS を開始します: dfs(0) を呼び出し、結果の最終値を確認します。

解決策の手順:

ツリーの構築: トラバースを容易にするために、エッジリストを隣接リストに変換します。
訪問先配列の初期化: 訪問先配列を使用して、ノードを再度訪問しないようにします。
DFS Traversal: ノード 0 から開始して DFS を実行します。ノードごとに、そのサブツリーの値の合計を計算します。
割り算のチェック: サブツリーの合計が k で割り切れる場合、結果をインクリメントし、サブツリーの合計を 0 にリセットします。
最終コンポーネントチェック: DFS トラバーサル後、ツリー全体 (ノード 0 をルートとする) の合計が k で割り切れるかどうかを確認し、必要に応じて別のコンポーネントとして考慮します。

このソリューションを PHP で実装してみましょう: 2872。 K で割り切れる成分の最大数

<?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
?>

ログイン後にコピー

説明：

ツリーの構築: ツリー構造を表す隣接リストを構築します。各エッジは 2 つのノードを接続し、この隣接リストを使用してツリーを走査します。
DFS Traversal: DFS 関数は、各ノードをルートとするサブツリーの合計を再帰的に計算します。サブツリーの合計が k で割り切れる場合、結果をインクリメントし、サブツリーを別の有効なコンポーネントとみなします。
サブツリーの合計を返す: 各ノードについて、DFS 関数はそのサブツリーの値の合計を返します。サブツリーが k で割り切れる場合は、合計 0 を返すことでエッジを事実上「カット」し、親ノードとのさらなるマージバックを防ぎます。
最終チェック: DFS の最後に、ツリー全体の合計が k で割り切れる場合、有効なコンポーネントとしてカウントされることを確認します。