Node Reachability on a DAG

Правка en1, от nchn27, 2019-06-30 07:08:24

You are given a DAG with N nodes and Q queries asking if node b can be reached from node a. Can this problem be solved for the likes of N = 10^5 and Q = 10^5?

Also I think if we are given a general directed graph, the problem can be turned into one on a DAG if we do SCC's?

Теги scc, dag, graph, graph theory

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский nchn27 2019-06-30 07:08:24 303 Initial revision (published)