Course Schedule IV Python Solution with Tests

lcpy gen -n 1462   # by problem number
lcpy gen -s course_schedule_iv   # by problem name

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.

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

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

class Solution:
    # Time: O(n^3) Floyd-Warshall transitive closure (n <= 100)
    # Space: O(n^2)
    def check_if_prerequisite(
        self, num_courses: int, prerequisites: list[list[int]], queries: list[list[int]]
    ) -> list[bool]:
        # reach[a][b] = True if a is a (direct or indirect) prerequisite of b.
        reach = [[False] * num_courses for _ in range(num_courses)]
        for a, b in prerequisites:
            reach[a][b] = True

        for k in range(num_courses):
            for i in range(num_courses):
                if reach[i][k]:
                    for j in range(num_courses):
                        if reach[k][j]:
                            reach[i][j] = True

        return [reach[u][v] for u, v in queries]