1462. Course Schedule IV

https://leetcode.com/problems/course-schedule-iv/

Some algorithm called Floyd-Warshall,

I was heading to a wrong direction at first (Topological sort) still don't know how to do it with topological sort algo

Related Problem:

Loading...LeetCode

For directed graph, for each query query[x][y] asks if x is preq of y

you want to know inside this graph if x and y is connected in this direction

class Solution:
    def checkIfPrerequisite(self, n: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:
        connected = [[False]*n for _ in range(n)]
        for pair in prerequisites:
            prev,course = pair
            connected[prev][course] = True
        
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    connected[i][j] = connected[i][j] or (connected[i][k] and connected[k][j])
        
        res = []
        for query in queries:
            x,y = query
            if connected[x][y]:
                res.append(True)
            else:
                res.append(False)
        return res