Diameters for each node of Tree after connecting it with given disconnected component | Java Program to implement the above approach ; 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 ; Driver Code ; constructed tree is 1 / \ 2 3 7 / | \ / | \ 4 5 6 ; creating undirected edges
import java . util . * ; class GFG { static int X = 1 ; static int diameter = 0 ; static HashMap < Integer , Boolean > mp = new HashMap < > ( ) ; static void dfs ( int current_node , int prev_node , int len , boolean add_to_map , Vector < Integer > [ ] adj ) { if ( len > diameter ) { diameter = len ; X = current_node ; } if ( add_to_map && len == diameter ) { mp . put ( current_node , true ) ; } for ( int it : adj [ current_node ] ) { if ( it != prev_node ) dfs ( it , current_node , len + 1 , add_to_map , adj ) ; } } static void dfsUtility ( Vector < Integer > [ ] adj ) { dfs ( 1 , - 1 , 0 , false , adj ) ; int farthest_node = X ; dfs ( farthest_node , - 1 , 0 , false , adj ) ; dfs ( farthest_node , - 1 , 0 , true , adj ) ; dfs ( X , - 1 , 0 , true , adj ) ; } static void printDiameters ( Vector < Integer > [ ] adj ) { dfsUtility ( adj ) ; for ( int i = 1 ; i <= 6 ; i ++ ) { if ( mp . containsKey ( i ) && mp . get ( i ) == true ) System . out . print ( diameter + 1 + " , ▁ " ) ; else System . out . print ( diameter + " , ▁ " ) ; } } public static void main ( String [ ] args ) { Vector < Integer > [ ] adj = new Vector [ 7 ] ; for ( int i = 0 ; i < adj . length ; i ++ ) adj [ i ] = new Vector < Integer > ( ) ; adj [ 1 ] . add ( 2 ) ; adj [ 2 ] . add ( 1 ) ; adj [ 1 ] . add ( 3 ) ; adj [ 3 ] . add ( 1 ) ; adj [ 2 ] . add ( 4 ) ; adj [ 4 ] . add ( 2 ) ; adj [ 2 ] . add ( 5 ) ; adj [ 5 ] . add ( 2 ) ; adj [ 2 ] . add ( 6 ) ; adj [ 6 ] . add ( 2 ) ; printDiameters ( adj ) ; } }