Maximum cost path in an Undirected Graph such that no edge is visited twice in a row | Java program for the above approach ; To store the resulting sum of the cost ; To store largest cost leaf vertex ; DFS Traversal to find the update the maximum cost of from any node to leaf ; Mark vertex as visited ; Store vertex initial cost ; Initially assuming edge not to be traversed ; Back edge found so , edge can be part of traversal ; New vertex is found ; Bitwise AND the current check with the returned check by the previous DFS Call ; Adds parent and its children cost ; Updates total cost of parent including child nodes ; Edge is part of the cycle ; Add cost of vertex to the answer ; Updates the largest cost leaf vertex ; Function to find the maximum cost from source vertex such that no two edges is traversed twice ; DFS call ; Print the maximum cost ; Driver Code ; Cost Array ; Given Graph ; Given Source Node ; Function call
import java . util . * ; class GFG { static int N = 100000 ; static int canTake ; static int best ; static int [ ] dp = new int [ N ] ; static boolean [ ] vis = new boolean [ N ] ; static boolean dfs ( Vector < Integer > [ ] g , int [ ] cost , int u , int pre ) { vis [ u ] = true ; dp [ u ] = cost [ u ] ; boolean check = true ; int cur = cost [ u ] ; for ( int x : g [ u ] ) { if ( vis [ x ] && x != pre ) { check = false ; } else if ( ! vis [ x ] ) { check = dfs ( g , cost , x , u ) ? false : true ; cur = Math . max ( cur , cost [ u ] + dp [ x ] ) ; } } dp [ u ] = cur ; if ( ! check ) { canTake += cost [ u ] ; } else { best = Math . max ( best , dp [ u ] ) ; } return check ; } static void FindMaxCost ( Vector < Integer > [ ] g , int [ ] cost , int source ) { dfs ( g , cost , source , - 1 ) ; System . out . print ( canTake + best ) ; } public static void main ( String [ ] args ) { int n = 5 , m = 5 ; int cost [ ] = { 2 , 2 , 8 , 6 , 9 } ; @ SuppressWarnings ( " unchecked " ) Vector < Integer > [ ] g = new Vector [ n ] ; for ( int i = 0 ; i < g . length ; i ++ ) g [ i ] = new Vector < Integer > ( ) ; g [ 0 ] . add ( 1 ) ; g [ 1 ] . add ( 0 ) ; g [ 0 ] . add ( 2 ) ; g [ 2 ] . add ( 0 ) ; g [ 0 ] . add ( 3 ) ; g [ 3 ] . add ( 0 ) ; g [ 1 ] . add ( 2 ) ; g [ 2 ] . add ( 1 ) ; g [ 1 ] . add ( 4 ) ; g [ 4 ] . add ( 1 ) ; int source = 1 ; FindMaxCost ( g , cost , source ) ; } }