1462. Course Schedule IV

[mah-shamim]

Discussed in #1232

^{Originally posted by mah-shamim January 27, 2025}
Topics: Depth-First Search, Breadth-First Search, Graph, Topological Sort

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course ai first if you want to take course bi.

• For example, the pair [0, 1] indicates that you have to take course 0 before you can take course 1.

Prerequisites can also be indirect. If course a is a prerequisite of course b, and course b is a prerequisite of course c, then course a is a prerequisite of course c.

You are also given an array queries where queries[j] = [uj, vj]. For the jth query, you should answer whether course uj is a prerequisite of course vj or not.

Return a boolean array answer, where answer[j] is the answer to the jth query.

Example 1:

• Input: numCourses = 2, prerequisites = [[1,0]], queries = [[0,1],[1,0]]
• Output: [false,true]
• Explanation: The pair [1, 0] indicates that you have to take course 1 before you can take course 0.
  Course 0 is not a prerequisite of course 1, but the opposite is true.

Example 2:

• Input: numCourses = 2, prerequisites = [], queries = [[1,0],[0,1]]
• Output: [false,false]
• Explanation: There are no prerequisites, and each course is independent.

Example 3:

• Input: numCourses = 3, prerequisites = [[1,2],[1,0],[2,0]], queries = [[1,0],[1,2]]
• Output: [true,true]

Constraints:

• 2 <= numCourses <= 100
• 0 <= prerequisites.length <= (numCourses * (numCourses - 1) / 2)
• prerequisites[i].length == 2
• 0 <= ai, bi <= numCourses - 1
• ai != bi
• All the pairs [ai, bi] are unique.
• The prerequisites graph has no cycles.
• 1 <= queries.length <= 104
• 0 <= ui, vi <= numCourses - 1
• ui != vi

Hint:

1. Imagine if the courses are nodes of a graph. We need to build an array isReachable[i][j].
2. Start a bfs from each course i and assign for each course j you visit isReachable[i][j] = True.
3. Answer the queries from the isReachable array.

[mah-shamim]

We can use a graph representation and the Floyd-Warshall algorithm to compute whether each course is reachable from another course. This approach will efficiently handle the prerequisite relationships and allow us to answer the queries directly.

Let's implement this solution in PHP: 1462. Course Schedule IV

<?php
/**
 * @param Integer $numCourses
 * @param Integer[][] $prerequisites
 * @param Integer[][] $queries
 * @return Boolean[]
 */
function checkIfPrerequisite($numCourses, $prerequisites, $queries) {
    // Step 1: Initialize the graph with false values
    $isReachable = array_fill(0, $numCourses, array_fill(0, $numCourses, false));

    // Step 2: Fill the graph with direct prerequisites
    foreach ($prerequisites as $prerequisite) {
        $isReachable[$prerequisite[0]][$prerequisite[1]] = true;
    }

    // Step 3: Use Floyd-Warshall algorithm to calculate transitive closure
    for ($k = 0; $k < $numCourses; $k++) {
        for ($i = 0; $i < $numCourses; $i++) {
            for ($j = 0; $j < $numCourses; $j++) {
                if ($isReachable[$i][$k] && $isReachable[$k][$j]) {
                    $isReachable[$i][$j] = true;
                }
            }
        }
    }

    // Step 4: Answer the queries
    $result = [];
    foreach ($queries as $query) {
        $result[] = $isReachable[$query[0]][$query[1]];
    }

    return $result;
}

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

Explanation:

1. Graph Initialization:

   • The $isReachable 2D array is initialized to false, representing that no course is reachable from another initially.

2. Direct Prerequisites:

   • We populate the $isReachable array based on the prerequisites. For every prerequisite [a, b], course a must be taken before course b.

3. Floyd-Warshall Algorithm:

   • This algorithm calculates the transitive closure of the graph.
   • For every intermediate course k, we check if course i is reachable from course j through k. If yes, we mark $isReachable[i][j] = true.

4. Query Evaluation:

   • Each query [u, v] is answered by simply checking the value of $isReachable[u][v].

Complexity:

• Time Complexity:
  • Floyd-Warshall algorithm: O(numCourses³)
  • Queries: O(queries.length)
  • Total: O(numCourses³ + queries.length)
• Space Complexity:
  • The space used by the $isReachable array is O(numCourses²).

Example Walkthrough:

Input:

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

Execution:

1. After initializing the graph:

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

2. After Floyd-Warshall:

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

3. Answering queries:

   • Query [1, 0]: true
   • Query [1, 2]: true

Output:

[true, true]