コーススケジュールIV

1462年。コーススケジュール IV

難易度: 中

トピック: 深さ優先検索、幅優先検索、グラフ、トポロジカルソート

受講する必要があるコースは合計 numCourses あり、0 から numCourses - 1 までのラベルが付けられています。prerequisites[i] = [a_i, b_{i という配列の前提条件が与えられます。} ] は、コースを受講する必要があることを示しますコースを受講したい場合は、まず a_i b_i.

• たとえば、[0, 1] のペアは、コース 1 を受講する前にコース 0 を受講する必要があることを示します。

前提条件は間接的にすることもできます。コース a がコース b の前提条件であり、コース b がコース c の前提条件である場合、コース a はコース c の前提条件となります。

queries[j] = [u_j, v_j] である配列クエリも与えられます。 j^番目のクエリについては、コース u_j がコース v_j の前提条件であるかどうかを答える必要があります。

ブール配列の回答を返します。ここで、answer[j] は j ^番目 クエリ に対する回答です。

例 1:

• 入力: numCourses = 2、前提条件 = [[1,0]]、クエリ = [[0,1],[1,0]]
• 出力: [false,true]
• 説明: [1, 0] のペアは、コース 0 を受講する前にコース 1 を受講する必要があることを示します。 コース 0 はコース 1 の前提条件ではありませんが、その逆が当てはまります。

例 2:

• 入力: numCourses = 2、前提条件 = []、クエリ = [[1,0],[0,1]]
• 出力: [false,false]
• 説明: 前提条件はなく、各コースは独立しています。

例 3:

• 入力: numCourses = 3、前提条件 = [[1,2],[1,0],[2,0]]、クエリ = [[1,0],[1,2]]
• 出力: [true,true]

制約:

• 2
• 0
• 前提条件[i].length == 2
• 0 _i, b_i
• a_i != b_i
• すべてのペア [a_i, b_i] は一意です。
• 前提条件グラフにはサイクルがありません。
• 1 4
• 0 _i, v_i
• u_i != v_i

ヒント:

1. コースがグラフのノードであるかどうかを想像してください。配列 isReachable[i][j].
を構築する必要があります。
2. 各コース i から bfs を開始し、訪問する各コース j に isReachable[i][j] = True を割り当てます。
3. isReachable 配列からのクエリに応答します。

解決策:

グラフ表現とフロイド・ウォーシャルアルゴリズムを使用して、各コースが別のコースから到達可能かどうかを計算できます。このアプローチにより、前提条件となる関係が効率的に処理され、クエリに直接答えることができるようになります。

このソリューションを PHP で実装してみましょう: 1462。コーススケジュール IV

<?php /**
 * @param Integer $numCourses
 * @param Integer[][] $prerequisites
 * @param Integer[][] $queries
 * @return Boolean[]
 */
function checkIfPrerequisite($numCourses, $prerequisites, $queries) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:

$numCourses = 2;
$prerequisites = [[1,0]];
$queries = [[0,1],[1,0]];

$result = checkIfPrerequisite($numCourses, $prerequisites, $queries);
print_r($result); // Output: [false,true]

$numCourses = 2;
$prerequisites = [];
$queries = [[1,0],[0,1]]

$result = checkIfPrerequisite($numCourses, $prerequisites, $queries);
print_r($result); // Output: [false,false]

$numCourses = 3;
$prerequisites = [[1, 2], [1, 0], [2, 0]];
$queries = [[1, 0], [1, 2]];

$result = checkIfPrerequisite($numCourses, $prerequisites, $queries);
print_r($result); // Output: [true, true]
?>

説明：

1. グラフの初期化:

   • $isReachable 2D 配列は false に初期化され、最初は他のコースから到達できないことを表します。

2. 直接の前提条件:

   • 前提条件に基づいて $isReachable 配列を設定します。すべての前提条件 [a、b] について、コース a をコース b の前に受講する必要があります。

3. フロイド・ウォーシャルアルゴリズム:

   • このアルゴリズムは、グラフの推移閉包を計算します。
   • すべての中級コース k について、コース i がコース j から k まで到達可能かどうかを確認します。 「はい」の場合、$isReachable[i][j] = true とマークします。

4. クエリ評価:

   • 各クエリ [u, v] は、$isReachable[u][v] の値をチェックするだけで答えられます。

複雑：

• 時間計算量:
  • フロイド・ウォーシャルアルゴリズム: O(numCourses³)
  • クエリ: O(queries.length)
  • 合計: O(コース数³ クエリ.長さ)
• 空間の複雑さ:
  • $isReachable 配列で使用されるスペースは O(numCourses²) です。

チュートリアルの例:

入力：

$numCourses = 3;
$prerequisites = [[1, 2], [1, 0], [2, 0]];
$queries = [[1, 0], [1, 2]];

実行：

1. グラフを初期化した後:

   $isReachable = [
       [false, false, false],
       [false, false, true],
       [false, false, false]
   ];

1. フロイド＝ウォーシャルの後:

   $isReachable = [
       [false, false, false],
       [true, false, true],
       [true, false, false]
   ];

1. クエリへの回答:
   • クエリ [1, 0]: true
   • クエリ [1, 2]: true

出力：

[true, true]

連絡先リンク

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

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

• LinkedIn
• GitHub

以上がコーススケジュールIVの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。