topological sort would cover every vertex once. The path given by Topological sort would be the answer. We can also calculate the vertices given by topological sort and compare it with given vertices. if it is same then graph G does contain a directed path that touches every vertex exactly once.
On Mon, Jul 12, 2010 at 10:08 AM, Love-143 <lovekesh6mn...@gmail.com> wrote: > Give a linear-time algorithm for the following task. > > Input: : A directed acyclic graph G (V,E) > Question: Does G contain a directed path that touches every vertex exactly > once? > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
