Is there a good way to respond to queries that ask if there’s a path between two nodes in a DAG? I know that O(1) and O(N^2) is possible with DFS preprocessing, but I’m looking for something with at least O(\log{N}) and O(N\log{N}) preprocessing. Am I missing something obvious?
Doesn’t look like it …
Is there a specific problem you’re working on?
Not really, I was just thinking about some ideas for topological sort.
Are you trying to count how many paths? Or just whether there exists a path?