VietCT's blog

DAG Queries
By VietCT, history, 5 years ago, In English

I wonder if we can solve this problem ?

Given a DAG $$$(n \lt = 3e5, m \lt = 3e5)$$$ and $$$Q$$$ queries $$$(Q \lt = 3e5)$$$ $$$u$$$ $$$v$$$, determine if $$$u$$$ is ancestor of $$$v$$$ in DAG

  • Vote: I like it
  • +25
  • Vote: I do not like it

»
5 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it
Hint
→ Reply
»
5 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

One simple (but not very nice) idea that I can think of is processing the queries offline. Find the topological sort of the dag and traverse from reverse and maintain bitsets.

→ Reply
»
5 years ago, hide # |
 
Vote: I like it +36 Vote: I do not like it

Since everyone is talking about bitsets, I want to note one thing — having $$$N$$$ bitsets of length $$$N$$$ will be more than 1 GB, which is more than the memory limit on most platforms (and I'm not sure how fast you can allocate it, either).

Instead, don't use bitsets, just long longs. Maintain dp[u], where dp[u] is a bitmask telling you which of the first 64 vertices are reachable from $$$u$$$. Then do the same thing for vertices 65...128 and so on. You'll make $$$\frac{N}{64}$$$ passes, each of them with time complexity $$$O(N)$$$, so you get the same complexity as the bitset solution without the memory implications.

(Note that this kills off online solutions...)

→ Reply