HideoSatou's blog

By HideoSatou, history, 5 years ago, In English

Given a planar directed acyclic graph with $$$N$$$ vertices and $$$M$$$ edges. Given $$$Q$$$ queries of type $$$(a, b)$$$. For each query, output "Yes" if it's possible to reach vertex $$$b$$$ from vertex $$$a$$$ and "No" otherwise.

$$$1 \le N, M, Q \le 300000$$$.

Is it possible to solve this problem under this constraints?

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

| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by HideoSatou (previous revision, new revision, compare).

»
5 years ago, # |
Rev. 3   Vote: I like it +31 Vote: I do not like it

It is possible to solve reachability problem on planar dag after O(n log(n)) preprocessing. Algorithm is explained here. https://en.wikipedia.org/wiki/Reachability#Thorup's_Algorithm