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
using System ; using System . Collections . Generic ; class GFG { static int ans ; static void DFS ( int src , List < List < int > > Adj , int [ ] arr , int currentMin , int currentMax ) { ans = Math . Max ( ans , Math . Max ( Math . Abs ( currentMax - arr [ src - 1 ] ) , Math . Abs ( currentMin - arr [ src - 1 ] ) ) ) ; currentMin = Math . Min ( currentMin , arr [ src - 1 ] ) ; currentMax = Math . Min ( currentMax , arr [ src - 1 ] ) ; foreach ( int child in Adj [ src ] ) { DFS ( child , Adj , arr , currentMin , currentMax ) ; } } static void getMaximumDifference ( int [ , ] Edges , int [ ] arr , int N , int M ) { ans = 0 ; List < List < int > > Adj = new List < List < int > > ( ) ; for ( int i = 0 ; i < N + 1 ; i ++ ) Adj . Add ( new List < int > ( ) ) ; for ( int i = 0 ; i < M ; i ++ ) { int u = Edges [ i , 0 ] ; int v = Edges [ i , 1 ] ; Adj [ u ] . Add ( v ) ; } DFS ( 1 , Adj , arr , arr [ 0 ] , arr [ 0 ] ) ; Console . WriteLine ( ans ) ; } static void Main ( ) { int N = 5 , M = 4 ; int [ , ] Edges = { { 1 , 2 } , { 2 , 3 } , { 4 , 5 } , { 1 , 3 } } ; int [ ] arr = { 13 , 8 , 3 , 15 , 18 } ; getMaximumDifference ( Edges , arr , N , M ) ; } }