Maximum cost path in an Undirected Graph such that no edge is visited twice in a row | Python3 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
N = 100000 NEW_LINE canTake = 0 NEW_LINE best = 0 NEW_LINE dp = [ 0 for i in range ( N ) ] NEW_LINE vis = [ 0 for i in range ( N ) ] NEW_LINE def dfs ( g , cost , u , pre ) : NEW_LINE INDENT global canTake , best NEW_LINE vis [ u ] = True NEW_LINE dp [ u ] = cost [ u ] NEW_LINE check = 1 NEW_LINE cur = cost [ u ] NEW_LINE for x in g [ u ] : NEW_LINE INDENT if ( vis [ x ] and x != pre ) : NEW_LINE INDENT check = 0 NEW_LINE DEDENT elif ( not vis [ x ] ) : NEW_LINE INDENT check &= dfs ( g , cost , x , u ) NEW_LINE cur = max ( cur , cost [ u ] + dp [ x ] ) NEW_LINE DEDENT DEDENT dp [ u ] = cur NEW_LINE if ( not check ) : NEW_LINE INDENT canTake += cost [ u ] NEW_LINE DEDENT else : NEW_LINE INDENT best = max ( best , dp [ u ] ) NEW_LINE DEDENT return check NEW_LINE DEDENT def FindMaxCost ( g , cost , source ) : NEW_LINE INDENT dfs ( g , cost , source , - 1 ) NEW_LINE print ( canTake + best ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT n = 5 NEW_LINE m = 5 NEW_LINE cost = [ 2 , 2 , 8 , 6 , 9 ] NEW_LINE g = [ [ ] for i in range ( n ) ] NEW_LINE g [ 0 ] . append ( 1 ) NEW_LINE g [ 1 ] . append ( 0 ) NEW_LINE g [ 0 ] . append ( 2 ) NEW_LINE g [ 2 ] . append ( 0 ) NEW_LINE g [ 0 ] . append ( 3 ) NEW_LINE g [ 3 ] . append ( 0 ) NEW_LINE g [ 1 ] . append ( 2 ) NEW_LINE g [ 2 ] . append ( 1 ) NEW_LINE g [ 1 ] . append ( 4 ) NEW_LINE g [ 4 ] . append ( 1 ) NEW_LINE source = 1 NEW_LINE FindMaxCost ( g , cost , source ) NEW_LINE DEDENT