Maximum difference between node and its ancestor in a Directed Acyclic Graph ( DAG ) | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; void DFS ( int src , vector < int > Adj [ ] , int & ans , int arr [ ] , int currentMin , int currentMax ) { ans = max ( ans , max ( abs ( currentMax - arr [ src - 1 ] ) , abs ( currentMin - arr [ src - 1 ] ) ) ) ; currentMin = min ( currentMin , arr [ src - 1 ] ) ; currentMax = min ( currentMax , arr [ src - 1 ] ) ; for ( auto & child : Adj [ src ] ) { DFS ( child , Adj , ans , arr , currentMin , currentMax ) ; } } void getMaximumDifference ( int Edges [ ] [ 2 ] , int arr [ ] , int N , int M ) { vector < int > Adj [ N + 1 ] ; for ( int i = 0 ; i < M ; i ++ ) { int u = Edges [ i ] [ 0 ] ; int v = Edges [ i ] [ 1 ] ; Adj [ u ] . push_back ( v ) ; } int ans = 0 ; DFS ( 1 , Adj , ans , arr , arr [ 0 ] , arr [ 0 ] ) ; cout << ans ; } int main ( ) { int N = 5 , M = 4 ; int Edges [ ] [ 2 ] = { { 1 , 2 } , { 2 , 3 } , { 4 , 5 } , { 1 , 3 } } ; int arr [ ] = { 13 , 8 , 3 , 15 , 18 } ; getMaximumDifference ( Edges , arr , N , M ) ; return 0 ; }