# 1462. Course Schedule IV """ there are a total of 'numCourses' courses that you have to take, labeled from 0 to 'numCourses - 1'. you are given an array 'prerequisites' where 'prerequisites[i] = [a_i, b_i]' indicates that you must take course 'a_i' before 'b_i'. 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] = [u_j, v_j]'. for the j'th query, you should answer whether course 'u_j' is a prerequisite of course 'v_j' or not. """ class Solution(object): def checkIfPrerequisite(self, numCourses, prerequisites, queries): """ :type numCourses: int :type prerequisites: List[List[int]] :type queries: List[List[int]] :rtype: List[bool] """ connected = [[False] * numCourses for i in range(numCourses)] for i, j in prerequisites: connected[i][j] = True for k in range(numCourses): for i in range(numCourses): for j in range(numCourses): connected[i][j] = connected[i][j] or ( connected[i][k] and connected[k][j] ) return [connected[i][j] for i, j in queries] if __name__ == "__main__": obj = Solution() print( obj.checkIfPrerequisite( numCourses=2, prerequisites=[[1, 0]], queries=[[0, 1], [1, 0]] ) ) print( obj.checkIfPrerequisite( numCourses=2, prerequisites=[], queries=[[1, 0], [0, 1]] ) ) print( obj.checkIfPrerequisite( numCourses=3, prerequisites=[[1, 2], [1, 0], [2, 0]], queries=[[1, 0], [1, 2]], ) )