Reachability Problem on Planar DAG

Revision en1, by HideoSatou, 2019-10-08 16:33:27

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?

Tags #graph theory, #graph_theory, #graph, #graphs

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English HideoSatou 2019-10-08 17:10:01 0 (published)
en1 English HideoSatou 2019-10-08 16:33:27 342 Initial revision (saved to drafts)