课程时间表IV

1462。课程表四

难度：中等

主题：深度优先搜索、广度优先搜索、图、拓扑排序

您必须修读总共 numCourses 课程，标记为从 0 到 numCourses - 1。您将获得一个数组先决条件，其中先决条件[i] = [a_i, b_i ] 表示您必须首先学习课程a_i，如果您想参加课程b_i.

• 例如，[0, 1]对表示您必须先选修课程 0，然后才能选修课程 1。

先决条件也可以是间接。如果课程a是课程b的先决条件，课程b是课程c的先决条件，那么课程a是课程c的先决条件。

您还会获得一个数组查询，其中querys[j] = [u_j, v_j]。对于第 j^th 查询，您应该回答课程 u_j 是否是课程 v_j 的先决条件。

返回一个布尔数组答案，其中answer[j]是第j^第查询的答案。

示例1：

• 输入： 课程数 = 2，先决条件 = [[1,0]]，查询 = [[0,1],[1,0]]
• 输出： [假，真]
• 说明： [1, 0] 对表示您必须先学习课程 1，然后才能学习课程 0。 课程 0 并不是课程 1 的先决条件，反之亦然。

示例2：

• 输入： 课程数 = 2，先决条件 = []，查询 = [[1,0],[0,1]]
• 输出： [假，假]
• 说明：没有先决条件，每门课程都是独立的。

示例 3：

• 输入： 课程数 = 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. 想象课程是否是图的节点。我们需要构建一个阵列[i] [j]。
>
2. >从每个课程i启动一个BFS，并为每个课程分配j您访问Isreach [i] [j] = true。
3. 回答来自Isreach Array的查询。

解决方案：

我们可以使用A图表>和floyd-warshall算法来计算是否可以从另一个课程到达每个课程。这种方法将有效地处理先决条件，并允许我们直接回答查询。

>

>让我们在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. >直接先决条件： >我们根据先决条件填充了$ ISREACH的阵列。对于每个先决条件[a，b]，必须在课程b。
> floyd-warshall算法：

3. 该算法计算图形的及传递闭合。>

   对于每个中级课程k，我们检查课程我是否可以从课程j到k到。如果是，我们将$ ISREACHABLE [i] [J] = true。
   • 查询评估：
4. 通过简单地检查$ ISREACHABLE [u] [v]。
   复杂：
   时间复杂性：

floyd-warshall算法：

o（numcourses
• 3 ）
  • QUERIES：o（queries.length）>
  总计：
  • o（numcourses3 queries.length）
  • 空间复杂性：
  $ isReachable数组使用的空间是
o（numcourses
• 2 ）
  。
  • ^{示例演练：} 输入：
  执行：

初始化图表后：

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

之后，弗洛伊德·瓦尔沙尔（Floyd-Warshall）：

回答查询：

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

QUERY [1，0]：true
查询[1，2]：true

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

1. 输出：
   联系链接

如果您发现此系列有帮助，请考虑在Github上给出 reposority >在您喜欢的社交网络上分享帖子？您的支持对我来说意义重大！>

[true, true]

如果您想要这样的更多有用的内容，请随时关注我：

>

LinkedIn

github

以上是课程时间表IV的详细内容。更多信息请关注PHP中文网其他相关文章！