Maximum product of two non | Java program to find maximum product of two non - intersecting paths ; Returns maximum length path in subtree rooted at u after removing edge connecting u and v ; To find lengths of first and second maximum in subtrees . currMax is to store overall maximum . ; Loop through all neighbors of u ; If neighbor is v , then skip it ; Call recursively with current neighbor as root ; Get max from one side and update ; Store total length by adding max and second max ; Update current max by adding 1 , i . e . current node is included ; Method returns maximum product of length of two non - intersecting paths ; One by one removing all edges and calling dfs on both subtrees ; Calling dfs on subtree rooted at g [ i ] [ j ] , excluding edge from g [ i ] [ j ] to i . ; Calling dfs on subtree rooted at i , edge from i to g [ i ] [ j ] ; Utility function to add an undirected edge ( u , v ) ; Driver code ; There are N edges , so + 1 for nodes and + 1 for 1 - based indexing
import java . util . * ; class GFG { static int curMax ; static int dfs ( Vector < Integer > g [ ] , int u , int v ) { int max1 = 0 , max2 = 0 , total = 0 ; for ( int i = 0 ; i < g [ u ] . size ( ) ; i ++ ) { if ( g [ u ] . get ( i ) == v ) continue ; total = Math . max ( total , dfs ( g , g [ u ] . get ( i ) , u ) ) ; if ( curMax > max1 ) { max2 = max1 ; max1 = curMax ; } else max2 = Math . max ( max2 , curMax ) ; } total = Math . max ( total , max1 + max2 ) ; curMax = max1 + 1 ; return total ; } static int maxProductOfTwoPaths ( Vector < Integer > g [ ] , int N ) { int res = Integer . MIN_VALUE ; int path1 , path2 ; for ( int i = 1 ; i < N + 2 ; i ++ ) { for ( int j = 0 ; j < g [ i ] . size ( ) ; j ++ ) { curMax = 0 ; path1 = dfs ( g , g [ i ] . get ( j ) , i ) ; curMax = 0 ; path2 = dfs ( g , i , g [ i ] . get ( j ) ) ; res = Math . max ( res , path1 * path2 ) ; } } return res ; } static void addEdge ( Vector < Integer > g [ ] , int u , int v ) { g [ u ] . add ( v ) ; g [ v ] . add ( u ) ; } public static void main ( String [ ] args ) { int edges [ ] [ ] = { { 1 , 8 } , { 2 , 6 } , { 3 , 1 } , { 5 , 3 } , { 7 , 8 } , { 8 , 4 } , { 8 , 6 } } ; int N = edges . length ; @ SuppressWarnings ( " unchecked " ) Vector < Integer > [ ] g = new Vector [ N + 2 ] ; for ( int i = 0 ; i < g . length ; i ++ ) g [ i ] = new Vector < Integer > ( ) ; for ( int i = 0 ; i < N ; i ++ ) addEdge ( g , edges [ i ] [ 0 ] , edges [ i ] [ 1 ] ) ; System . out . print ( maxProductOfTwoPaths ( g , N ) + "NEW_LINE"); } }