Course Schedule IV
Understanding the Problem
We're given a directed acyclic graph (DAG) where each edge [a, b] means "course a must be taken before course b." Each query [u, v] asks whether course u is a prerequisite of course v. Indirect prerequisites count, so if u reaches v through any chain of edges, the answer is true.
The challenge is efficiency. We could answer each query independently by running a graph search, but that repeats work when there are thousands of queries. The alternative is to precompute reachability for the entire graph once, then answer each query in O(1).
This is a transitive closure problem: given a directed graph, determine for every pair (u, v) whether there's a path from u to v.
Key Constraints:
numCourses <= 100→ With at most 100 nodes, an O(n^3) algorithm costs about a million operations, so Floyd-Warshall is affordable.prerequisites.length <= n*(n-1)/2→ The graph can be dense, up to ~5,000 edges for n=100, which matters when choosing between edge-driven and matrix-based algorithms.queries.length <= 10^4→ Up to 10,000 queries. If we precompute reachability, each query is O(1). Without precomputation, running BFS/DFS per query gives O(q * (n + e)), which is about 50 million operations. Precomputation is the better strategy.- The graph has no cycles, so it's a DAG. This opens up topological sort-based approaches.
Approach 1: BFS/DFS for Each Query
Intuition
For each query [u, v], run a BFS or DFS starting from node u and check whether the search reaches node v. If it does, the answer is true. Otherwise, it's false.
This is correct and simple, but it repeats work. Queries that start from the same node traverse the same portion of the graph again, and nothing learned during one search carries over to the next.
Algorithm
- Build an adjacency list from the prerequisites.
- For each query [u, v], run a BFS/DFS starting from u.
- If the search visits v, add true to the result. Otherwise, add false.
- Return the result list.
Visualization and Code
Loading animation...
- Time Complexity: O(q * (n + e)). For each of the q queries, we run a BFS that visits up to n nodes and e edges. With q up to 10^4 and n + e up to about 5,100, this is around 50 million operations in the worst case.
- Space Complexity: O(n + e). The adjacency list takes O(n + e) space. Each BFS uses an O(n) visited array and queue.
A partial fix is to cache results per source: run BFS at most once for each distinct starting node and reuse its visited set across queries, for O(n * (n + e)) total search work. Precomputing reachability for every pair goes one step further and makes each query a table lookup.
Approach 2: Floyd-Warshall (Transitive Closure)
Intuition
Instead of answering queries one at a time, build a complete reachability matrix: for every pair of nodes (i, j), record whether i can reach j. Once the matrix exists, every query is a constant-time lookup.
The Floyd-Warshall algorithm computes this. Originally designed for all-pairs shortest paths, the same triple loop computes transitive closure: for each intermediate node k, check whether going through k connects a pair (i, j). If i can reach k and k can reach j, then i can reach j.
With n at most 100, the O(n^3) cost is about one million operations.
The invariant: after the outer loop finishes iteration k, reachable[i][j] is true exactly when some path from i to j uses only intermediate nodes from {0, ..., k}. Direct edges establish the base case. For the inductive step, a path with intermediates in {0, ..., k} either avoids k entirely, which the previous iteration already recorded, or passes through k once, splitting into an i-to-k segment and a k-to-j segment whose intermediates all come from {0, ..., k-1}. Both segments were recorded by earlier iterations, so the check reachable[i][k] && reachable[k][j] catches the path.
This is also why k must be the outermost loop: the i and j loops need values that are already complete for intermediates up to k-1, and swapping the loop order breaks that guarantee.
Algorithm
- Create an n x n boolean matrix
reachable, initialized to all false. - For each prerequisite edge [a, b], set
reachable[a][b] = true. - Run Floyd-Warshall: for each intermediate node k (0 to n-1), for each pair (i, j), if
reachable[i][k]andreachable[k][j]are both true, setreachable[i][j] = true. - For each query [u, v], return
reachable[u][v].
Visualization and Code
Loading animation...
- Time Complexity: O(n^3 + q). The three nested loops for Floyd-Warshall run in O(n^3). With n = 100, that's about 10^6 operations. Answering q queries takes O(q) total since each is a constant-time lookup.
- Space Complexity: O(n^2). The reachability matrix is n x n. With n = 100, that's 10,000 booleans, which is negligible.
The triple loop updates one boolean at a time. Packing each row of the matrix into machine words lets the inner loop process 64 entries per operation.
Approach 3: Bitset Floyd-Warshall
Intuition
Row i of the reachability matrix is a sequence of n booleans, one per course. Stored as a bitset, the entire inner j loop of Floyd-Warshall collapses into one row-wide OR: if i reaches k, then everything k reaches becomes reachable from i, written as reach[i] |= reach[k]. A 64-bit word covers 64 matrix entries at once, so the n^3 single-boolean updates become about n^2 * n/64 word operations.
Merging whole rows is safe because row k cannot change during iteration k. The only update that could touch it is OR-ing row k into itself, which leaves it unchanged. So every row merged into row i is identical to what the element-by-element version would have read.
Algorithm
- Create one bit row per course. For each prerequisite edge [a, b], set bit b in row a.
- For each intermediate node k from 0 to n-1: for every row i whose bit k is set, OR row k into row i.
- For each query [u, v], answer with bit v of row u.
Visualization and Code
Loading animation...
- Time Complexity: O(n^3 / 64 + q). The k and i loops still run n^2 times, but each merge handles 64 matrix entries per word operation, so the total is about n^2 * (n / 64) word operations: roughly 16,000 for n = 100. Each query reads one bit, so q queries cost O(q).
- Space Complexity: O(n^2 / 64). The matrix stores n^2 bits packed into machine words, about 1.3 KB for n = 100.
Every Floyd-Warshall variant does work proportional to n^3 (divided by the word size at best) no matter how many edges exist. The final approach uses the DAG structure directly and propagates reachability only along actual edges.
Approach 4: Topological Sort with Reachability Propagation
Intuition
Since the graph is a DAG, we can process nodes in topological order: when a node is processed, every node that points into it has already been processed, so reachability information can be pushed forward along edges.
Each node maintains a set of all nodes that are prerequisites of it (its ancestors). When we process a node u with a neighbor v (meaning u is a prerequisite of v), we add u and all of u's ancestors to v's ancestor set. After every node is processed, a query [u, v] is a membership check on v's ancestor set.
Each edge triggers a set union of up to n elements, so propagation costs O(n * e) in the worst case. On sparse graphs this beats Floyd-Warshall's fixed O(n^3); on dense graphs, where e approaches n^2/2, the two are comparable and the bitset version wins on constants.
A node enters the queue only when its in-degree reaches zero, which happens after every one of its direct predecessors has been dequeued and has pushed its ancestor set forward. By induction along the dequeue order: the first nodes dequeued have no predecessors, so their empty ancestor sets are trivially complete. Every later node is dequeued only after receiving the complete ancestor set of each predecessor, plus the predecessors themselves. So each node's ancestor set is complete at the moment it is dequeued, and the information it propagates onward is final.
Algorithm
- Build an adjacency list and compute in-degrees for each node.
- Initialize a queue with all nodes that have in-degree 0 (no prerequisites).
- For each node, maintain a set of all its ancestors (prerequisites).
- Process nodes in topological order (BFS with in-degree tracking):
- Dequeue a node u.
- For each neighbor v of u: add u to v's ancestor set, union u's ancestor set into v's ancestor set, and decrement v's in-degree. If v's in-degree reaches 0, enqueue it.
- For each query [u, v], check if u is in v's ancestor set.
Visualization and Code
Loading animation...
- Time Complexity: O(n e + q). Building the graph takes O(n + e). The topological sort processes each edge once, but each edge unions a set of up to n elements into another, so propagation work is O(n e). Answering q queries takes O(q) since each set lookup is O(1) average.
- Space Complexity: O(n^2 + e). Each of the n ancestor sets can hold up to n elements, so total set storage is O(n^2). The adjacency list takes O(n + e) space.