Find farthest node from each node in Tree | C ++ implementation to find the farthest node from each vertex of the tree ; Adjacency list to store edges ; Add edge between U and V in tree ; Edge from U to V ; Edge from V to U ; DFS to find the first End Node of diameter ; Calculating level of nodes ; Go in opposite direction of parent ; Function to clear the levels of the nodes ; set all value of lvl [ ] to 0 for next dfs ; Set maximum with 0 ; DFS will calculate second end of the diameter ; Calculating level of nodes ; Store the node with maximum depth from end1 ; Go in opposite direction of parent ; Function to find the distance of the farthest distant node ; Storing distance from end1 to node u ; Function to find the distance of nodes from second end of diameter ; storing distance from end2 to node u ; Joining Edge between two nodes of the tree ; Find the one end of the diameter of tree ; Find the other end of the diameter of tree ; Find the distance to each node from end1 ; Find the distance to each node from end2 ; Comparing distance between the two ends of diameter ; Driver code ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define N  10000 NEW_LINE vector < int > adj [ N ] ; int lvl [ N ] , dist1 [ N ] , dist2 [ N ] ; void AddEdge ( int u , int v ) { adj [ u ] . push_back ( v ) ; adj [ v ] . push_back ( u ) ; } int end1 , end2 , maxi ; void findFirstEnd ( int u , int p ) { lvl [ u ] = 1 + lvl [ p ] ; if ( lvl [ u ] > maxi ) { maxi = lvl [ u ] ; end1 = u ; } for ( int i = 0 ; i < adj [ u ] . size ( ) ; i ++ ) { if ( adj [ u ] [ i ] != p ) { findFirstEnd ( adj [ u ] [ i ] , u ) ; } } } void clear ( int n ) { for ( int i = 0 ; i <= n ; i ++ ) { lvl [ i ] = 0 ; } maxi = 0 ; dist1 [ 0 ] = dist2 [ 0 ] = -1 ; } void findSecondEnd ( int u , int p ) { lvl [ u ] = 1 + lvl [ p ] ; if ( lvl [ u ] > maxi ) { maxi = lvl [ u ] ; end2 = u ; } for ( int i = 0 ; i < adj [ u ] . size ( ) ; i ++ ) { if ( adj [ u ] [ i ] != p ) { findSecondEnd ( adj [ u ] [ i ] , u ) ; } } } void findDistancefromFirst ( int u , int p ) { dist1 [ u ] = 1 + dist1 [ p ] ; for ( int i = 0 ; i < adj [ u ] . size ( ) ; i ++ ) { if ( adj [ u ] [ i ] != p ) { findDistancefromFirst ( adj [ u ] [ i ] , u ) ; } } } void findDistancefromSecond ( int u , int p ) { dist2 [ u ] = 1 + dist2 [ p ] ; for ( int i = 0 ; i < adj [ u ] . size ( ) ; i ++ ) { if ( adj [ u ] [ i ] != p ) { findDistancefromSecond ( adj [ u ] [ i ] , u ) ; } } } void findNodes ( ) { int n = 5 ; AddEdge ( 1 , 2 ) ; AddEdge ( 1 , 3 ) ; AddEdge ( 3 , 4 ) ; AddEdge ( 3 , 5 ) ; findFirstEnd ( 1 , 0 ) ; clear ( n ) ; findSecondEnd ( end1 , 0 ) ; findDistancefromFirst ( end1 , 0 ) ; findDistancefromSecond ( end2 , 0 ) ; for ( int i = 1 ; i <= n ; i ++ ) { int x = dist1 [ i ] ; int y = dist2 [ i ] ; if ( x >= y ) { cout << end1 << ' ▁ ' ; } else { cout << end2 << ' ▁ ' ; } } } int main ( ) { findNodes ( ) ; return 0 ; }