Hi, What I am trying to say is this. a. Do a DFS on the given graph G to get connected components C1...Ck b. Consider Ci (i) I claim that every pair of nodes in the connected component is connected to every other node in the same connected component (say you have arbitrary points A,B in Ci, go from (A to root(Ci) to B), similarly B is connected to A.
On Tue, Nov 24, 2009 at 10:13 PM, Rohit Saraf <rohit.kumar.sa...@gmail.com>wrote: > But then .. > think.. > for every two pairs of nodes you have to check whether both are connected > to root and then you will say yes/no. > And you will have to do this for all disjoint components. > It's right but not O(n^2). > Ya, DFS has all this rolled into one run of O(n+e) All this is assuming that the graph is undirected. > -- > 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.
