On Sat, May 11, 2013 at 10:29 AM, Aman Jain <pureama...@gmail.com> wrote:
> 2. from this no*de u*, again apply* dfs* to find longest distant node > from this node.Let us say that node is v. > Small doubt about the solution. Consider this graph a -> b -> c -> d You randomly choose vertex 'b' and do a DFS. Your "u" will be vertex 'd'. Then you do DFS from d, but its out degree is 0. So your DFS ends at 'd' itself and you report the solution as b->c->d. But the solution is a->b->c->d. What did I miss? My proposal: Topological Sort <http://en.wikipedia.org/wiki/Topological_sorting> the graph and keep removing the nodes from vertices which have out degree of 0 (given the DAG, there will always be atleast one such vertex). Rest is self explanatory :) Veni Vedi Slumber ! -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
