Problem Breakdown
We are given courses labeled 0 to n-1. We have a list of direct prerequisites where [u, v] implies course u must be taken before course v, defining a directed edge from u to v. Additionally, we receive multiple queries asking if there is an indirect or direct path from one course to another (i.e., is A a prerequisite of B?).
Key Inputs:
n: Number of courses.prerequisites: List of[from_course, to_course]pairs defining the DAG structure.queries: List of[u, v]asking if there exists a path fromutov.
Key Outputs:
- A list of booleans corresponding to each query in order.
Constraints & Edge Cases:
- is small (), but the number of queries can be large (). This suggests we should not process every query independently if it involves graph traversal, as that would lead to Time Limit Exceeded (TLE) in Python. We need a precomputation strategy.
- The graph is guaranteed acyclic (DAG), so no infinite loops during traversal logic.
- Queries might ask about non-existent paths or disconnected components; these should return
false.
Intuition
A naive approach would be to run a Breadth-First Search (BFS) or Depth-First Search (DFS) from the source course for every single query to check reachability. Complexity of Brute Force: For each query, we traverse nodes/edges. With queries and potentially dense graphs (), this results in roughly . Given and , operations could approach , which is risky for Python’s execution time limits.
Optimal Insight: Since the number of courses () is very small, we can precompute the reachability between all pairs of nodes (Transitive Closure). Once we know if u reaches v, any query takes to answer. We can compute this closure using the Floyd-Warshall algorithm or by running a BFS/DFS from every node once and storing results in an adjacency matrix. Given , Floyd-Warshall’s complexity of operations is negligible compared to processing the queries efficiently.
Approach
- Initialize Matrix: Create a boolean adjacency matrix
reachof size . Initialize all values toFalse. - Populate Direct Edges: Iterate through
prerequisites. For each[u, v], setreach[u][v] = True. Note that the problem defines prerequisites such that if we have a pair[1,0], it means course 1 is required for course 0 (edge ). - Compute Transitive Closure: Use Floyd-Warshall logic to fill in indirect paths. For every intermediate node
kfrom0ton-1:- If there is a path from
itokAND a path fromktoj, then mark that there is a path fromitoj. - Update:
reach[i][j] = reach[i][j] or (reach[i][k] and reach[k][j]).
- If there is a path from
- Answer Queries: Iterate through the
querieslist. For each query[u, v], check ifreach[u][v]is true. Append result to output list.
Complexity Analysis
- Time Complexity: . The Floyd-Warshall loop runs in cubic time relative to the number of courses ( ops). Answering queries takes linear time with respect to query count. This is highly efficient given constraints.
- Space Complexity: . We store an adjacency matrix for the reachability information ( booleans), which uses minimal memory compared to input storage requirements.
Solution
from typing import List
class Solution:
def checkIfPrerequisite(self, n: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:
# Initialize reachability matrix with False (0)
is_reachable = [[False] * n for _ in range(n)]
# Populate direct edges from prerequisites input
# Note: [u, v] means u must be taken before v -> edge u -> v
for u, v in prerequisites:
is_reachable[u][v] = True
# Floyd-Warshall Algorithm to compute Transitive Closure
# k iterates through intermediate nodes
for k in range(n):
for i in range(n):
if is_reachable[i][k]: # If path exists from i -> k
row_k = is_reachable[k]
for j in range(n):
if row_k[j]: # And path exists from k -> j
is_reachable[i][j] = True
# Answer queries using the precomputed matrix
result = []
for u, v in queries:
result.append(is_reachable[u][v])
return result