Diameters for each node of Tree after connecting it with given disconnected component | Keeps track of the farthest end of the diameter ; Keeps track of the length of the diameter ; Stores the nodes which are at ends of the diameter ; Perform DFS on the given tree ; Update diameter and X ; If current node is an end of diameter ; Traverse its neighbors ; Function to call DFS for the required purposes ; DFS from a random node and find the node farthest from it ; DFS from X to calculate diameter ; DFS from farthest_node to find the farthest node ( s ) from it ; DFS from X ( other end of diameter ) and check the farthest node ( s ) from it ; If node i is the end of a diameter ; Increase diameter by 1 ; Otherwise ; Remains unchanged ; constructed tree is 1 / \ 2 3 7 / | \ / | \ 4 5 6 ; creating undirected edges
let X = 1 ; let diameter = 0 ; let mp = new Map ( ) ; function dfs ( current_node , prev_node , len , add_to_map , adj ) { if ( len > diameter ) { diameter = len ; X = current_node ; } if ( add_to_map && len == diameter ) { mp . set ( current_node , true ) ; } for ( let it = 0 ; it < adj [ current_node ] . length ; it ++ ) { if ( adj [ current_node ] [ it ] != prev_node ) dfs ( adj [ current_node ] [ it ] , current_node , len + 1 , add_to_map , adj ) ; } } function dfsUtility ( adj ) { dfs ( 1 , - 1 , 0 , false , adj ) ; let farthest_node = X ; dfs ( farthest_node , - 1 , 0 , false , adj ) ; dfs ( farthest_node , - 1 , 0 , true , adj ) ; dfs ( X , - 1 , 0 , true , adj ) ; } function printDiameters ( adj ) { dfsUtility ( adj ) ; for ( let i = 1 ; i <= 6 ; i ++ ) { if ( mp . has ( i ) && mp . get ( i ) == true ) document . write ( diameter + 1 + " " ) ; else document . write ( diameter + " " ) ; } } let adj = new Array ( 7 ) ; for ( let i = 0 ; i < adj . length ; i ++ ) adj [ i ] = [ ] ; adj [ 1 ] . push ( 2 ) ; adj [ 2 ] . push ( 1 ) ; adj [ 1 ] . push ( 3 ) ; adj [ 3 ] . push ( 1 ) ; adj [ 2 ] . push ( 4 ) ; adj [ 4 ] . push ( 2 ) ; adj [ 2 ] . push ( 5 ) ; adj [ 5 ] . push ( 2 ) ; adj [ 2 ] . push ( 6 ) ; adj [ 6 ] . push ( 2 ) ; printDiameters ( adj ) ;