@Gene : Smooth :) How did I miss such an elegant solution..Duh
_dufus On Sep 13, 7:27 am, Gene <gene.ress...@gmail.com> wrote: > On Sep 6, 5:28 am, ankur aggarwal <ankur.mast....@gmail.com> wrote: > > > google question : find triangle in a graph Given an undirected graph, > > design a O(V+E) algo to detect whether there is a triangle in the graph ot > > not. > > Just do a depth first search, numbering each node with it's depth as > you find it. If you are searching from a node at depth D and discover > a back-edge to depth D - 2, you have found a triangle. It's pretty > easy to show that if no such back-edges are found, there are no > triangles. --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@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 -~----------~----~----~----~------~----~------~--~---