DAG Reachability Queries with Preprocessing
You have a directed acyclic graph (DAG) with $n$ nodes and $m$ edges. You need to answer $Q$ queries of the form: "is there a path from node $u$ to node $v$?" where $Q$ can be as large as
0^5$.
The naive approach -- running a BFS/DFS per query -- costs $O(Q \cdot (n + m))$ total, which is too slow when $Q$ is large.
Design a preprocessing scheme so that individual queries can be answered faster. You do not need a single solution -- there is a spectrum of approaches with different time/space tradeoffs. Describe at least two distinct approaches, state their preprocessing time, query time, and space usage, and explain the tradeoffs.
**Constraints:**
-
\leq n \leq 10^4$
-
\leq m \leq 10^5$
-
\leq Q \leq 10^5$
- The graph is guaranteed to be a DAG (no cycles)
**Example:**
Nodes: $\{1, 2, 3, 4\}$, Edges:
\to 2$,
\to 3$, \to 4$
Query $(1, 3)$: Yes -- path
\to 2 \to 3$ exists.
Query $(4, 2)$: No -- no path from $4$ to
$.
Query $(1, 4)$: Yes -- direct edge.Open the full interactive solver, hints, and worked solution →