Reachability Problem on Planar DAG

Правка en1, от 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?

Теги #graph theory, #graph_theory, #graph, #graphs

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский HideoSatou 2019-10-08 17:10:01 0 (published)
en1 Английский HideoSatou 2019-10-08 16:33:27 342 Initial revision (saved to drafts)