Diameters for each node of Tree after connecting it with given disconnected component | Python3 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 ; constructed tree is 1 / \ 2 3 / | \ 4 5 6 | 7 ; Creating undirected edges
from collections import defaultdict NEW_LINE X = 1 NEW_LINE diameter = 0 NEW_LINE mp = defaultdict ( lambda : 0 ) NEW_LINE def dfs ( current_node , prev_node , len , add_to_map , adj ) : NEW_LINE INDENT global diameter , X NEW_LINE if len > diameter : NEW_LINE INDENT diameter = len NEW_LINE X = current_node NEW_LINE DEDENT if add_to_map and len == diameter : NEW_LINE INDENT mp [ current_node ] = 1 NEW_LINE DEDENT for it in adj [ current_node ] : NEW_LINE INDENT if it != prev_node : NEW_LINE INDENT dfs ( it , current_node , len + 1 , add_to_map , adj ) NEW_LINE DEDENT DEDENT DEDENT def dfsUtility ( adj ) : NEW_LINE INDENT dfs ( 1 , - 1 , 0 , 0 , adj ) NEW_LINE farthest_node = X NEW_LINE dfs ( farthest_node , - 1 , 0 , 0 , adj ) NEW_LINE dfs ( farthest_node , - 1 , 0 , 1 , adj ) NEW_LINE dfs ( X , - 1 , 0 , 1 , adj ) NEW_LINE DEDENT def printDiameters ( adj ) : NEW_LINE INDENT global diameter NEW_LINE dfsUtility ( adj ) NEW_LINE for i in range ( 1 , 6 + 1 ) : NEW_LINE INDENT if mp [ i ] == 1 : NEW_LINE INDENT print ( diameter + 1 , end = " , ▁ " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( diameter , end = " , ▁ " ) NEW_LINE DEDENT DEDENT DEDENT adj = [ ] NEW_LINE for i in range ( 7 ) : NEW_LINE INDENT adj . append ( [ ] ) NEW_LINE DEDENT adj [ 1 ] . append ( 2 ) NEW_LINE adj [ 2 ] . append ( 1 ) NEW_LINE adj [ 1 ] . append ( 3 ) NEW_LINE adj [ 3 ] . append ( 1 ) NEW_LINE adj [ 2 ] . append ( 4 ) NEW_LINE adj [ 4 ] . append ( 2 ) NEW_LINE adj [ 2 ] . append ( 5 ) NEW_LINE adj [ 5 ] . append ( 2 ) NEW_LINE adj [ 2 ] . append ( 6 ) NEW_LINE adj [ 6 ] . append ( 2 ) NEW_LINE printDiameters ( adj ) NEW_LINE