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 ?
Common Ancestor in a Directed Acyclic Graph (DAG)
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 ?
Rev. | Язык | Кто | Когда | Δ | Комментарий | |
---|---|---|---|---|---|---|
en1 | zeref_dragoneel | 2015-08-27 07:02:23 | 207 | Initial revision (published) |