Course Schedule IV

Intuition

A query asks whether one course can be reached from another by following prerequisite edges, so the core object we need is reachability between every pair of courses. Since numCourses is at most 100, we can afford a full n-by-n boolean matrix that records whether i reaches j. We seed the matrix with the direct edges, then repeatedly propagate: if i reaches k and k reaches j, then i reaches j. This is exactly the Floyd-Warshall idea applied to boolean OR instead of shortest paths. Once the closure is complete, each of the possibly many queries is a single matrix lookup.

Algorithm walkthrough

1. 1Allocate an n-by-n boolean matrix reachable, initialized to false.
2. 2For every prerequisite [a, b], set reachable[a][b] = true to record the direct edges.
3. 3Run three nested loops over intermediate node k, source i, and destination j; whenever reachable[i][k] and reachable[k][j] are both true, mark reachable[i][j] = true.
4. 4After the triple loop, reachable[u][v] is true exactly when u is a prerequisite of v, directly or indirectly.
5. 5For each query [u, v], append reachable[u][v] to the answer.
6. 6Return the collected boolean array.

Implementation

class Solution:
    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:
        reachable = [[False] * numCourses for _ in range(numCourses)]
        for u, v in prerequisites:
            reachable[u][v] = True
        for k in range(numCourses):
            for i in range(numCourses):
                if reachable[i][k]:
                    for j in range(numCourses):
                        if reachable[k][j]:
                            reachable[i][j] = True
        return [reachable[u][v] for u, v in queries]