Problem:
Given a directed graph and $$$q$$$ queries. For each query, you need to answer whether a path exists from point $$$x$$$ to point $$$y$$$. Each query needs to be processed within $$$O(1)$$$.
A BF solution is, we can do $$$V$$$ DFSs from every vertex and set the bits in the answer matrix for each visited vertex, and the complexity of preprocessing is $$$O(V^2)$$$. You can do some optimizations to reduce the steps taken in the traversal by a lot, but as long as you store the answer in a matrix, $$$O(V^2)$$$ space complexity leads to an inevitable $$$O(V^2)$$$ time complexity.
Now the question is: is it possible to do the preprocessing within less than $$$O(V^2)$$$ time, or at least, less than $$$O(V^2)$$$ space? At least, if queries are to be processed online, it seems highly improbable.
I wrote DAG in the title, because we can run Tarjan's to find out SCCs and if $$$x$$$ and $$$y$$$ belong to the same SCC it's a clear YES.
UPD: There seems to be some paper on this: Paper
trick 1 from this blog
I think this only reduced the constant factor, instead of the complexity
It reduces the time complexity from $$$O(n^2)$$$ to $$$O(n^2/ \log{n})$$$ and memory from $$$O(n^2/ \log{n})$$$ to $$$O(n)$$$.
If you want to reduce the time complexity even further, consider getting treatment to increase your IQ and invent a way yourself.
Well, reducing from
bitset<V>tolong long[V/64]does not necessarily cut the space cost by an order of complexity.Did you even read the blog?
Stop asking questions if you do not want to listen to the answers.
If you read the blog and do not understand why the space taken is only $$$O(n \log{n} / \log{n}) = O(n)$$$, then you are probably too weak to understand this technique right now, try again later.
It depends of the architecture of the computer, so we can't talk about a real Time Complexity Analysis.
I mean we can use optimized Disjoint Set Union? For every edge, do
union_sets(u, v).Now when given a query, check if
find_set(u) == find_set(v)? This will achieve almost O(1) time complexity for each query and O(n) space complexity. Learn more about TC here.Edit:
I noticed that you were asking for DAG, this approach would work for undirected graph.
Reachability on DAG is not commutative ;)
Compress graph to DAG first
Now store N bitsets, with bits representing reachable nodes from u. Now for each u simply do dp[u] |= dp[v]. Which will have O(n^2/32) both time and space complexity, but in practice it'll work extremely fast for even N <= 10^5 and sometimes even 2*10^5, depending on constraints and compiller. Common practice is to use pragma (target "popcount" if I remember correctly). Iirc you can't do it any better unless graph has some special structure