Common Ancestor in a Directed Acyclic Graph (DAG)

Правка en1, от zeref_dragoneel, 2015-08-27 07:02:23

I need to find all pairs of nodes which have a common ancestor in a DAG in O(n^2 + m) time. I can use O(n^2 memory).

Please suggest a method to do this ?

Теги graphs, dag, lca

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский zeref_dragoneel 2015-08-27 07:02:23 207 Initial revision (published)