DAG Reachability Queries with Preprocessing
You have a directed acyclic graph (DAG) with $n$ nodes (labeled $0 \ldots n-1$) and $m$ edges. You need to answer $Q$ reachability queries of the form: "is there a directed path from node $u$ to node $v$?" A node always reaches itself ($u = v \to$ True).
Implement the function:
```python def dag_reachability(n, edges, queries): ... ```
n: number of nodes (labeled0..n-1).edges: list of[u, v]directed edges (guaranteed acyclic).queries: list of[u, v]pairs.
Return a list of booleans, one per query, in order: True if v is reachable from u following directed edges, else False.
The naive approach -- running a BFS/DFS per query at $O(n + m)$ each -- costs $O(Q \cdot (n + m))$ total, too slow when $Q$ is large. Design a preprocessing scheme (e.g. compute reachability once over the topological order) so queries are answered fast.
Constraints: - $1 \leq n \leq 10^4$ - $1 \leq m \leq 10^5$ - $1 \leq Q \leq 10^5$ - The graph is guaranteed to be a DAG (no cycles).
Example
dag_reachability(4, [[0,1],[1,2],[0,3]], [[0,2],[3,1],[0,3],[2,2]]) -> [True, False, True, True]
Because $0 \to 1 \to 2$ makes 2 reachable from 0 (True); there is no path from 3 to 1 (False); $0 \to 3$ is a direct edge (True); and a node always reaches itself, so $(2,2)$ is True.
Hints
- A DAG has a topological ordering -- think about how reachability information can be propagated backward through that ordering rather than recomputed per query.
- Consider representing each node's reachable set as a bitset of length $n$. Taking the union of two reachability sets then becomes a bitwise OR, which processes 64 nodes at a time.
- Process nodes in reverse topological order. For each node $u$, initialize $\text{reach}[u] = \{u\}$, then for each outgoing edge $u \to v$, union in $\text{reach}[v]$. After the pass, $\text{reach}[u]$ contains all nodes reachable from $u$.
Worked Solution
How to Think About It: The brute-force baseline is BFS/DFS per query at $O(n + m)$ each, so $Q$ queries cost $O(Q(n+m))$ -- far too slow when $Q$ is large. The insight is that a DAG has a topological order, which lets you propagate reachability information systematically during preprocessing rather than rediscovering it on every query.
Key Insight: If node $u$ can reach $v$, and $v$ can reach $w$, then $u$ can reach $w$. Process nodes in reverse topological order and union each node's reachability set from its successors. Storing each set as a bitmask makes the union a single bitwise OR.
Algorithm (Bitmask Transitive Closure):
- Topologically sort the DAG with Kahn's algorithm: $O(n + m)$.
- Initialize
reach[u]with just the bit for $u$ (a node reaches itself). - For each node $u$ in reverse topological order, OR in
reach[v]for every edge $u \to v$. - Answer each query $(u, v)$ in $O(1)$ by testing bit $v$ of
reach[u].
Preprocessing is $O(nm/64)$ with bitmasks; each query is $O(1)$.
Contract note: dag_reachability(n, edges, queries) must return a list of booleans (one per query, in order) -- not a reachability matrix and not a per-call boolean.
Code:
```python from collections import defaultdict, deque
def dag_reachability(n, edges, queries): # n nodes labeled 0..n-1. edges = list of [u, v] directed edges (a DAG). # queries = list of [u, v]; for each, answer whether v is reachable from u # following directed edges. A node reaches itself (u == v -> True). # Return a list of booleans, one per query, in order. adj = defaultdict(list) indegree = [0] * n for u, v in edges: adj[u].append(v) indegree[v] += 1
# Kahn's algorithm for topological sort queue = deque(i for i in range(n) if indegree[i] == 0) topo = [] while queue: node = queue.popleft() topo.append(node) for nb in adj[node]: indegree[nb] -= 1 if indegree[nb] == 0: queue.append(nb)
# Bitmask DP in reverse topological order: reach[u] = set of nodes reachable from u reach = [1 << i for i in range(n)] # each node reaches itself for u in reversed(topo): for v in adj[u]: reach[u] |= reach[v]
return [bool(reach[u] & (1 << v)) for u, v in queries] ```
Complexity Summary:
| Approach | Preprocessing | Query | Space | |---|---|---|---| | Naive BFS per query | None | $O(n + m)$ | $O(n + m)$ | | Bitmask transitive closure | $O(nm / 64)$ | $O(1)$ | $O(n^2 / 64)$ | | Interval / DFS-timestamp labeling | $O(n + m)$ | $O(\log n)$ | $O(m)$ |
For moderate $n$, bitmask DP on the topological order is the clean default: $O(1)$ queries after $O(nm/64)$ preprocessing. For very large sparse graphs where $O(n^2/64)$ space is prohibitive, interval/DFS-timestamp methods trade slightly slower queries for lower space.
Intuition
The core principle here is the preprocessing-query tradeoff: you are trading upfront computation and memory for faster answers at query time. This tradeoff appears constantly in systems design -- database indexes, precomputed lookup tables, memoized DP. The question is always: how much offline work can you afford, given the query load?
The bitmask trick is worth internalizing. Whenever you have a set of $n$ boolean values and need to compute unions repeatedly, packing them into 64-bit integers and using bitwise OR gives you a 64x speedup over naive element-by-element merging. This is not a theoretical trick -- it shows up in practice in graph reachability, state machine simulation, and constraint propagation. The DAG structure is what makes the DP valid: because there are no cycles, processing nodes in reverse topological order guarantees that when you look at $\text{reach}[v]$ for a neighbor $v$ of $u$, $\text{reach}[v]$ is already fully computed.