VietCT's blog

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

I wonder if we can solve this problem ?

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

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

»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it
Hint
→ Reply
»
3 years ago, # |
  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
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Well queries can be processed online as well, after the process.

    → Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 3   Vote: I like it +16 Vote: I do not like it

    It's actually the only possible idea for now (deciding if the task can be solved in subquadratic time is an open problem).

    → Reply
»
3 years ago, # |
  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