In graph theory, a tree is 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) The center of a tree is 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 valid tree as defined above. Output the node labels of the center(or centers) of the tree. 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 [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
