Course Schedule IV

How it works

The Floyd-Warshall algorithm finds all-pairs reachability in a graph. We can adapt it to find transitive closure: if there is a path from A to B through any intermediate course K, then A is a prerequisite of B. After running the algorithm, we have direct O(1) lookup for any pair.

Steps

1. Create a 2D boolean matrix initialized to false.
2. Mark direct prerequisites as true in the matrix.
3. For each intermediate course k, iterate through all pairs (i, j).
4. If there is a path from i to k and from k to j, mark the path from i to j as true.
5. For each query (u, v), simply return the value at matrix[u][v].

Complexity

• Time complexity: O(V ^ 3 + E + m)
• Space complexity: O(V ^ 2 + E + m)

Where m is the number of queries, V is the number of courses, and E is the number of prerequisites.

Things to watch for

Confusing Edge Direction

A common mistake is building the graph with edges pointing in the wrong direction. The prerequisite [a, b] means course a must be taken before course b, so a -> b. Reversing this leads to incorrect reachability results.

Rerunning DFS for Every Query Without Memoization

Running a fresh DFS for each query without caching results leads to repeated work. With many queries, this causes TLE. Always memoize visited pairs or precompute the full transitive closure.

Not Handling Disconnected Nodes

Courses with no prerequisites and no dependents are still valid nodes. Forgetting to initialize them in your adjacency list or prerequisite map causes KeyError or incorrect results when they appear in queries.

from typing import List

class Solution:
    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:
        res = []
        adj = [[False] * numCourses for _ in range(numCourses)]

        for pre, crs in prerequisites:
            adj[pre][crs] = True

        for k in range(numCourses):
            for i in range(numCourses):
                for j in range(numCourses):
                    adj[i][j] = adj[i][j] or (adj[i][k] and adj[k][j])

        for u, v in queries:
            res.append(adj[u][v])

        return res

class Solution {
public:
    vector<bool> checkIfPrerequisite(int numCourses, vector<vector<int>>& prerequisites, vector<vector<int>>& queries) {
        vector<vector<bool>> adj(numCourses, vector<bool>(numCourses, false));
        vector<bool> res;

        for (auto& pre : prerequisites) {
            adj[pre[0]][pre[1]] = true;
        }

        for (int k = 0; k < numCourses; k++) {
            for (int i = 0; i < numCourses; i++) {
                for (int j = 0; j < numCourses; j++) {
                    adj[i][j] = adj[i][j] || (adj[i][k] && adj[k][j]);
                }
            }
        }

        for (auto& q : queries) {
            res.push_back(adj[q[0]][q[1]]);
        }

        return res;
    }
};