the question is clear..you draw the sample test case and work out .. you will understand
1 / / \ 4 2 3 /\ 5 6 ....here from node 2 the maximum cost to reach any node 'i' is 2 and minimum is 1 ...so M(2) = max(1,2)=2..the same is the case for node 1 also ...if you consider node 4 , to reach 6 , cost is 3....similar is applicable for other nodes.... ....therefore centre = min(M(1..6)) = 1 and 2. ...hope u got me!! On Wed, Jul 27, 2011 at 2:08 AM, siva viknesh <sivavikne...@gmail.com>wrote: > > > > ---------- Forwarded message ---------- > From: jayapriya surendran <priya7...@gmail.com> > Date: Sep 29 2010, 9:41 pm > Subject: Directi question-centre of the tree > To: Algorithm Geeks > > > In graph theory, atreeis defined as a graph on N nodes,and (N-1) > un-directed edges such that there are no cycles in the graph.Each node > has a single unique path to every other node. > Let D(u,v) be the number of edges in the unique path from node 'u' to > node 'v' (or from node 'v' to 'u' since the edges are > un-directed).D(u,u) is 0 for all nodes 'u'. > M(u)=MAX(D(u,i):for all nodes i) > Thecenterof atreeis the node (or nodes) 'u',for which M(u) is > minimum among all the nodes in the graph. > You'll be given a graph which has N nodes (1<=N<=20).The nodes are > labeled 1,2,3,..N.You will be provided with N-1 edges in the form of > "a b" pairs where 1<=a,b<=N.No edge will be repeated.You can assume > that the edges are specified such that the graph is a validtreeas > defined above. > Output the node labels of thecenter(or centers) of thetree. > Sample Input: > 6(value of N) > 1 3 (edges) > 1 4 > 1 2 > 2 5 > 2 6 > > Sample Output > 1 > 2 > Expected:O(N) complexity algo > can anyone plz help me out with O(N) algo? > -- Regards, $iva -- 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?hl=en.