Diameters for each node of Tree after connecting it with given disconnected component | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int X = 1 ; int diameter = 0 ; map < int , bool > mp ; void dfs ( int current_node , int prev_node , int len , bool add_to_map , vector < vector < int > > & adj ) { if ( len > diameter ) { diameter = len ; X = current_node ; } if ( add_to_map && len == diameter ) { mp [ current_node ] = 1 ; } for ( auto & it : adj [ current_node ] ) { if ( it != prev_node ) dfs ( it , current_node , len + 1 , add_to_map , adj ) ; } } void dfsUtility ( vector < vector < int > > & adj ) { dfs ( 1 , -1 , 0 , 0 , adj ) ; int farthest_node = X ; dfs ( farthest_node , -1 , 0 , 0 , adj ) ; dfs ( farthest_node , -1 , 0 , 1 , adj ) ; dfs ( X , -1 , 0 , 1 , adj ) ; } void printDiameters ( vector < vector < int > > & adj ) { dfsUtility ( adj ) ; for ( int i = 1 ; i <= 6 ; i ++ ) { if ( mp [ i ] == 1 ) cout << diameter + 1 << " , ▁ " ; else cout << diameter << " , ▁ " ; } } int main ( ) { vector < vector < int > > adj ( 7 ) ; adj [ 1 ] . push_back ( 2 ) ; adj [ 2 ] . push_back ( 1 ) ; adj [ 1 ] . push_back ( 3 ) ; adj [ 3 ] . push_back ( 1 ) ; adj [ 2 ] . push_back ( 4 ) ; adj [ 4 ] . push_back ( 2 ) ; adj [ 2 ] . push_back ( 5 ) ; adj [ 5 ] . push_back ( 2 ) ; adj [ 2 ] . push_back ( 6 ) ; adj [ 6 ] . push_back ( 2 ) ; printDiameters ( adj ) ; return 0 ; }