---------- 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?
--
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.
