Maximum difference between node and its ancestor in a Directed Acyclic Graph ( DAG ) | Python3 program for the above approach ; Function to perform DFS Traversal on the given graph ; Update the value of ans ; Update the currentMin and currentMax ; Traverse the adjacency list of the node src ; Recursively call for the child node ; Function to calculate maximum absolute difference between a node and its ancestor ; Stores the adjacency list of graph ; Create Adjacency list ; Add a directed edge ; Perform DFS Traversal ; Print the maximum absolute difference ; Driver Code
ans = 0 NEW_LINE def DFS ( src , Adj , arr , currentMin , currentMax ) : NEW_LINE INDENT global ans NEW_LINE ans = max ( ans , max ( abs ( currentMax - arr [ src - 1 ] ) , abs ( currentMin - arr [ src - 1 ] ) ) ) NEW_LINE currentMin = min ( currentMin , arr [ src - 1 ] ) NEW_LINE currentMax = min ( currentMax , arr [ src - 1 ] ) NEW_LINE for child in Adj [ src ] : NEW_LINE INDENT DFS ( child , Adj , arr , currentMin , currentMax ) NEW_LINE DEDENT DEDENT def getMaximumDifference ( Edges , arr , N , M ) : NEW_LINE INDENT global ans NEW_LINE Adj = [ [ ] for i in range ( N + 1 ) ] NEW_LINE for i in range ( M ) : NEW_LINE INDENT u = Edges [ i ] [ 0 ] NEW_LINE v = Edges [ i ] [ 1 ] NEW_LINE Adj [ u ] . append ( v ) NEW_LINE DEDENT DFS ( 1 , Adj , arr , arr [ 0 ] , arr [ 0 ] ) NEW_LINE print ( ans ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT N = 5 NEW_LINE M = 4 NEW_LINE Edges = [ [ 1 , 2 ] , [ 2 , 3 ] , [ 4 , 5 ] , [ 1 , 3 ] ] NEW_LINE arr = [ 13 , 8 , 3 , 15 , 18 ] NEW_LINE getMaximumDifference ( Edges , arr , N , M ) NEW_LINE DEDENT