チャンピオン II を探せ

2924。チャンピオン II を探せ

難易度: 中

トピック: グラフ

トーナメントには 0 から n - 1 までの番号が付けられた n チームがあります。各チームは DAG のノードでもあります。

整数 n と、DAG を表す長さ m の 0 インデックス付き 2D 整数配列エッジが与えられます。ここで、>dges[i] = [u _i, v_i] は、チームからの有向エッジがあることを示しますu_i からチーム v_i をグラフに表示します。

グラフ内の a から b への有向辺は、チーム a がチーム b より強い、チーム b がチーム a より弱いことを意味します。

チーム a より強いチーム b が存在しない場合、チーム a がトーナメントのチャンピオンとなります。

ユニークなチャンピオンがいる場合はトーナメントのチャンピオンとなるチームを返します。それ以外の場合は、-1を返します。

メモ

• サイクルは、一連のノード a1_、a2_、...、an_、an 1 _{では、ノード a}1 _{がノードと同じノードになりますa}n 1_{、ノード a}1_、a2_、...、an _{は個別であり、有向範囲内のすべての i について、ノード a}i _{からノード a}i 1 _{までのエッジ[1, n].}
• DAG は、サイクル を持たない有向グラフです。

例 1:

• 入力: n = 3、エッジ = [[0,1],[1,2]]
• 出力: 0
• 説明: チーム 1 はチーム 0 より弱いです。チーム 2 はチーム 1 より弱いです。したがって、チャンピオンはチーム 0 です。

例 2:

• 入力: n = 4、エッジ = [[0,2],[1,3],[1,2]]
• 出力: -1
• 説明: チーム 2 はチーム 0 およびチーム 1 より弱いです。チーム 3 はチーム 1 より弱いです。しかし、チーム 1 とチーム 0 は他のどのチームよりも弱いわけではありません。したがって、答えは -1 です。

制約:

1 m == エッジ.長さ
0 edges[i].length == 2
0 エッジ[i][0] != エッジ[i][1]
チーム a がチーム b より強い場合、チーム b はチーム a より強くないように入力が生成されます。
チーム a がチーム b より強く、チーム b がチーム c より強い場合、チーム a がチーム c より強いように入力が生成されます。

ヒント:

1. チャンピオンは DAG 内で次数 0 を持つ必要があります。

解決策:

指定された有向非巡回グラフ (DAG) で 次数 が 0 のチームを識別する必要があります。流入エッジがないチームは、他のどのチームよりも強いチームを表しており、チャンピオンの候補となります。入次数が 0 のチームが 1 つだけ存在する場合、それが固有のチャンピオンになります。そのようなチームが複数ある場合、またはそのようなチームがない場合、結果は -1 になります。

このソリューションを PHP で実装してみましょう: 2924。チャンピオン II を探す

<?php
/**
 * @param Integer $n
 * @param Integer[][] $edges
 * @return Integer
 */
function findChampion($n, $edges) {
    // Initialize in-degrees for all teams
    $inDegree = array_fill(0, $n, 0);

    // Calculate the in-degree for each team
    foreach ($edges as $edge) {
        $inDegree[$edge[1]]++;
    }

    // Find teams with in-degree 0
    $candidates = [];
    for ($i = 0; $i < $n; $i++) {
        if ($inDegree[$i] == 0) {
            $candidates[] = $i;
        }
    }

    // If exactly one team has in-degree 0, return it; otherwise, return -1
    return count($candidates) === 1 ? $candidates[0] : -1;
}

// Example 1
$n1 = 3;
$edges1 = [[0, 1], [1, 2]];
echo "Example 1 Output: " . findChampion($n1, $edges1) . PHP_EOL; // Output: 0

// Example 2
$n2 = 4;
$edges2 = [[0, 2], [1, 3], [1, 2]];
echo "Example 2 Output: " . findChampion($n2, $edges2) . PHP_EOL; // Output: -1
?>

説明：

1. 入力解析:

   • n はチームの数です。
   • edges は、グラフ内の有向エッジのリストです。

2. 次数の初期化:

   • 0 に初期化されたサイズ n の配列 inDegree を作成します。

3. 次数を計算:

   • 各エッジ [u, v] について、v の入次数を増分します (チーム v にはもう 1 つの入力エッジがあります)。

4. 候補を検索:

   • inDegree 配列を反復処理し、in-degree が 0 であるインデックスを収集します。これらのインデックスは、他に強いチームが存在しないチームを表します。

5. チャンピオンを決定:

   • ちょうど 1 つのチームが内次数 0 を持っている場合、それが唯一のチャンピオンです。
   • 複数のチームまたは次数 0 を持つチームがない場合は、-1 を返します。

チュートリアルの例

例 1:

• 入力: n = 3、エッジ = [[0, 1], [1, 2]]
• 次数: [0, 1, 1]
• 次数 0 のチーム: [0]
• 出力: 0 (チーム 0 が唯一のチャンピオンです)。

例 2:

• 入力: n = 4、エッジ = [[0, 2], [1, 3], [1, 2]]
• 次数: [0, 0, 2, 1]
• 次数 0 のチーム: [0, 1]
• 出力: -1 (複数の潜在的なチャンピオンがいます)。

複雑さの分析

1. 時間計算量:

   • 度数の計算: O(m)、m はエッジの数です。
   • チームの確認: O(n)、n はチームの数です。
   • 合計: O(n m).

2. 空間の複雑さ:

   • inDegree 配列: O(n).

このソリューションは効率的であり、指定された制約内で機能します。

連絡先リンク

このシリーズが役立つと思われた場合は、GitHub で リポジトリ にスターを付けるか、お気に入りのソーシャル ネットワークで投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味を持ちます!

このような役立つコンテンツがさらに必要な場合は、お気軽にフォローしてください:

• LinkedIn
• GitHub

以上がチャンピオン II を探せの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。