[Deleted]

Seems like top sort. You can use the half idea of SCC. Problem link please?

There's a well-known approach for finding all such pairs using bitsets. Let's say that the vertices are numbered $$$0$$$ through $$$N-1$$$ in reverse topological order and for each vertex $$$v$$$, there's a bitset with $$$v$$$ bits where the $$$u$$$-th bit is 1 if there's a path from $$$v$$$ to $$$u$$$. For each edge $$$v \rightarrow u$$$, you just OR the bitset for $$$v$$$ with the bitset for $$$u$$$ and make sure the $$$u$$$-th bit is also $$$1$$$ (since that wasn't in the bitset).

This takes $$$N^2/2$$$ bits of memory, which is approx. 600 MB, and at most $$$NM/64$$$ bitwise operations (on a 64-bit machine), which is approx. 150 million, with no extra cache misses. Not that much.

I think it should be possible to process all queries offline using the smaller-to-larger optimization.

I got one idea, however I'm not sure if it will work, maybe some of the more experienced coders could check my work.

For simplicity, Let's assume that the there is just one vertex with no parents.

Let's start by picking one DFS tree of the given DAG (rooted at the node without parents). Now, we can notice that since the graph is DAG each edge in the graph will either be tree edge or edge that link current node to some other subtree. For each node we keep list of all the subtrees this node has links. It seems pretty clear that node $$$u$$$ is reachable from node $$$v$$$ if $$$u$$$ is in some subtree of $$$v$$$.

With clever implementation and using binary search we can store all the subtrees each node has links to and we can answer each query in $$$O(\log N)$$$.