Diferencia máxima entre el Node y su ancestro en un gráfico acíclico dirigido (DAG)

Dada una array 2D Edges[][] , que representa un borde dirigido entre el par de Nodes en un gráfico conectado acíclico dirigido que consta de N Nodes valorados de [1, N] y una array arr[] que representa los pesos de cada Node, la tarea es encontrar la máxima diferencia absoluta entre los pesos de cualquier Node y cualquiera de sus ancestros .

Ejemplos:

Explicación:

Del gráfico anterior, se puede observar que la diferencia máxima entre el valor de cualquier Node y cualquiera de sus ancestros es 18 (Node 5) – 8 (Node 2) = 10.

Enfoque: la idea para resolver el problema dado es realizar DFS Traversal en el gráfico y completar los valores máximos y mínimos de cada Node a su Node secundario y encontrar la diferencia absoluta máxima.
Siga los pasos a continuación para resolver el problema dado:

• Inicialice una variable, digamos ans como INT_MIN para almacenar la diferencia máxima requerida.
• Realice un recorrido DFS en el gráfico dado para encontrar la diferencia absoluta máxima entre los pesos de un Node y cualquiera de sus ancestros realizando las siguientes operaciones:
  • Para cada Node fuente, digamos src , actualice el valor de ans para almacenar el máximo de la diferencia absoluta entre el peso de src y currentMin y currentMax respectivamente.
  • Actualice el valor de currentMin como el mínimo de currentMin y el valor del Node de origen src .
  • Actualice el valor de currentMax como el máximo de currentMax y el valor del Node de origen src .
  • Ahora, recorra recursivamente los Nodes secundarios de src y actualice los valores de currentMax y currentMin como DFS(child, Adj, ans, currentMin, currentMax) .
• Después de completar los pasos anteriores, imprima el valor de ans como la diferencia máxima resultante.

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to perform DFS
// Traversal on the given graph
void DFS(int src, vector<int> Adj[],
         int& ans, int arr[],
         int currentMin, int currentMax)
{
 
    // Update the value of ans
    ans = max(
        ans, max(abs(
                     currentMax - arr[src - 1]),
                 abs(currentMin - arr[src - 1])));
 
    // Update the currentMin and currentMax
    currentMin = min(currentMin,
                     arr[src - 1]);
 
    currentMax = min(currentMax,
                     arr[src - 1]);
 
    // Traverse the adjacency
    // list of the node src
    for (auto& child : Adj[src]) {
 
        // Recursively call
        // for the child node
        DFS(child, Adj, ans, arr,
            currentMin, currentMax);
    }
}
 
// Function to calculate maximum absolute
// difference between a node and its ancestor
void getMaximumDifference(int Edges[][2],
                          int arr[], int N,
                          int M)
{
 
    // Stores the adjacency list of graph
    vector<int> Adj[N + 1];
 
    // Create Adjacency list
    for (int i = 0; i < M; i++) {
        int u = Edges[i][0];
        int v = Edges[i][1];
 
        // Add a directed edge
        Adj[u].push_back(v);
    }
 
    int ans = 0;
 
    // Perform DFS Traversal
    DFS(1, Adj, ans, arr,
        arr[0], arr[0]);
 
    // Print the maximum
    // absolute difference
    cout << ans;
}
 
// Driver Code
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;
}

// Java program for the above approach
import java.util.*;
 
class GFG{
     
static int ans;
 
// Function to perform DFS
// Traversal on the given graph
static void DFS(int src,
                ArrayList<ArrayList<Integer> > Adj,
                int arr[], int currentMin,
                int currentMax)
{
     
    // Update the value of ans
    ans = Math.max(ans,
          Math.max(Math.abs(currentMax - arr[src - 1]),
                   Math.abs(currentMin - arr[src - 1])));
 
    // Update the currentMin and currentMax
    currentMin = Math.min(currentMin, arr[src - 1]);
 
    currentMax = Math.min(currentMax, arr[src - 1]);
 
    // Traverse the adjacency
    // list of the node src
    for(Integer child : Adj.get(src))
    {
         
        // Recursively call
        // for the child node
        DFS(child, Adj, arr, currentMin, currentMax);
    }
}
 
// Function to calculate maximum absolute
// difference between a node and its ancestor
static void getMaximumDifference(int Edges[][],
                                 int arr[], int N,
                                 int M)
{
    ans = 0;
     
    // Stores the adjacency list of graph
    ArrayList<ArrayList<Integer>> Adj = new ArrayList<>();
 
    for(int i = 0; i < N + 1; i++)
        Adj.add(new ArrayList<>());
 
    // Create Adjacency list
    for(int i = 0; i < M; i++)
    {
        int u = Edges[i][0];
        int v = Edges[i][1];
 
        // Add a directed edge
        Adj.get(u).add(v);
    }
 
    // Perform DFS Traversal
    DFS(1, Adj, arr, arr[0], arr[0]);
 
    // Print the maximum
    // absolute difference
    System.out.println(ans);
}
 
// Driver code
public static void main(String[] args)
{
    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);
}
}
 
// This code is contributed by offbeat

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

// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG {
     
    static int ans;
  
    // Function to perform DFS
    // Traversal on the given graph
    static void DFS(int src, List<List<int>> Adj, int[] arr,
                    int currentMin, int currentMax)
    {
          
        // Update the value of ans
        ans = Math.Max(ans,
              Math.Max(Math.Abs(currentMax - arr[src - 1]),
                       Math.Abs(currentMin - arr[src - 1])));
      
        // Update the currentMin and currentMax
        currentMin = Math.Min(currentMin, arr[src - 1]);
      
        currentMax = Math.Min(currentMax, arr[src - 1]);
      
        // Traverse the adjacency
        // list of the node src
        foreach(int child in Adj[src])
        {
              
            // Recursively call
            // for the child node
            DFS(child, Adj, arr, currentMin, currentMax);
        }
    }
      
    // Function to calculate maximum absolute
    // difference between a node and its ancestor
    static void getMaximumDifference(int[,] Edges,
                                     int[] arr, int N, int M)
    {
        ans = 0;
          
        // Stores the adjacency list of graph
        List<List<int>> Adj = new List<List<int>>();
      
        for(int i = 0; i < N + 1; i++)
            Adj.Add(new List<int>());
      
        // Create Adjacency list
        for(int i = 0; i < M; i++)
        {
            int u = Edges[i,0];
            int v = Edges[i,1];
      
            // Add a directed edge
            Adj[u].Add(v);
        }
      
        // Perform DFS Traversal
        DFS(1, Adj, arr, arr[0], arr[0]);
      
        // Print the maximum
        // absolute difference
        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);
  }
}
 
// This code is contributed by rameshtravel07.

<script>
 
// Javascript program for the above approach
 
var ans = 0;
 
// Function to perform DFS
// Traversal on the given graph
function DFS(src, Adj, arr, currentMin, currentMax)
{
 
    // Update the value of ans
    ans = Math.max(
        ans, Math.max(Math.abs(
                     currentMax - arr[src - 1]),
                 Math.abs(currentMin - arr[src - 1])));
 
    // Update the currentMin and currentMax
    currentMin = Math.min(currentMin,
                     arr[src - 1]);
 
    currentMax = Math.min(currentMax,
                     arr[src - 1]);
 
    // Traverse the adjacency
    // list of the node src
    Adj[src].forEach(child => {
       
        // Recursively call
        // for the child node
        DFS(child, Adj,arr,
            currentMin, currentMax);
    });
}
 
// Function to calculate maximum absolute
// difference between a node and its ancestor
function getMaximumDifference(Edges, arr, N, M)
{
 
    // Stores the adjacency list of graph
    var Adj = Array.from(Array(N+1), ()=> Array());
 
    // Create Adjacency list
    for (var i = 0; i < M; i++) {
        var u = Edges[i][0];
        var v = Edges[i][1];
 
        // Add a directed edge
        Adj[u].push(v);
    }
 
    // Perform DFS Traversal
    DFS(1, Adj, arr,
        arr[0], arr[0]);
 
    // Print the maximum
    // absolute difference
    document.write( ans);
}
 
// Driver Code
var N = 5, M = 4;
var Edges
    = [ [ 1, 2 ], [ 2, 3 ],
        [ 4, 5 ], [ 1, 3 ] ];
var arr = [13, 8, 3, 15, 18];
getMaximumDifference(Edges, arr, N, M);
 
</script>

10

Complejidad temporal: O(N + M)
Espacio auxiliar: O(N)