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 <[email protected]> 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 [email protected]. > To unsubscribe from this group, send email to > [email protected]<algogeeks%[email protected]> > . > 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 [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
