Find triplet such that number of nodes connecting these triplets is maximum | Java implementation of the approach ; To store the required nodes ; Parent array to retrace the nodes ; Visited array to prevent DFS in direction on Diameter path ; DFS function to find the startnode ; DFS function to find the endnode of diameter and maintain the parent array ; DFS function to find the end node of the Longest Branch to Diameter ; Function to find the required nodes ; To find start node of diameter ; To find end node of diameter ; x is the end node of diameter ; Mark all the nodes on diameter using back tracking ; Find the end node of longest branch to diameter ; Driver code
import java . util . * ; class GFG { static int MAX = 100005 ; static Vector < Vector < Integer > > adjacent = new Vector < Vector < Integer > > ( ) ; static boolean visited [ ] = new boolean [ MAX ] ; static int startnode , endnode , thirdnode ; static int maxi = - 1 , N ; static int parent [ ] = new int [ MAX ] ; static boolean vis [ ] = new boolean [ MAX ] ; static void dfs ( int u , int count ) { visited [ u ] = true ; int temp = 0 ; for ( int i = 0 ; i < adjacent . get ( u ) . size ( ) ; i ++ ) { if ( ! visited [ adjacent . get ( u ) . get ( i ) ] ) { temp ++ ; dfs ( adjacent . get ( u ) . get ( i ) , count + 1 ) ; } } if ( temp == 0 ) { if ( maxi < count ) { maxi = count ; startnode = u ; } } } static void dfs1 ( int u , int count ) { visited [ u ] = true ; int temp = 0 ; for ( int i = 0 ; i < adjacent . get ( u ) . size ( ) ; i ++ ) { if ( ! visited [ adjacent . get ( u ) . get ( i ) ] ) { temp ++ ; parent [ adjacent . get ( u ) . get ( i ) ] = u ; dfs1 ( adjacent . get ( u ) . get ( i ) , count + 1 ) ; } } if ( temp == 0 ) { if ( maxi < count ) { maxi = count ; endnode = u ; } } } static void dfs2 ( int u , int count ) { visited [ u ] = true ; int temp = 0 ; for ( int i = 0 ; i < adjacent . get ( u ) . size ( ) ; i ++ ) { if ( ! visited [ adjacent . get ( u ) . get ( i ) ] && ! vis [ adjacent . get ( u ) . get ( i ) ] ) { temp ++ ; dfs2 ( adjacent . get ( u ) . get ( i ) , count + 1 ) ; } } if ( temp == 0 ) { if ( maxi < count ) { maxi = count ; thirdnode = u ; } } } static void findNodes ( ) { dfs ( 1 , 0 ) ; for ( int i = 0 ; i <= N ; i ++ ) visited [ i ] = false ; maxi = - 1 ; dfs1 ( startnode , 0 ) ; for ( int i = 0 ; i <= N ; i ++ ) visited [ i ] = false ; int x = endnode ; vis [ startnode ] = true ; while ( x != startnode ) { vis [ x ] = true ; x = parent [ x ] ; } maxi = - 1 ; for ( int i = 1 ; i <= N ; i ++ ) { if ( vis [ i ] ) dfs2 ( i , 0 ) ; } } public static void main ( String args [ ] ) { for ( int i = 0 ; i < MAX ; i ++ ) adjacent . add ( new Vector < Integer > ( ) ) ; N = 4 ; adjacent . get ( 1 ) . add ( 2 ) ; adjacent . get ( 2 ) . add ( 1 ) ; adjacent . get ( 1 ) . add ( 3 ) ; adjacent . get ( 3 ) . add ( 1 ) ; adjacent . get ( 1 ) . add ( 4 ) ; adjacent . get ( 4 ) . add ( 1 ) ; findNodes ( ) ; System . out . print ( " ( " + startnode + " , ▁ " + endnode + " , ▁ " + thirdnode + " ) " ) ; } }