Dado un árbol N-ario que tiene N Nodes con valores positivos y negativos y (N – 1) aristas, la tarea es encontrar la máxima diferencia absoluta de la suma de niveles en él.
Ejemplos:
Entrada: N = 8, Bordes[][2] = {{0, 1}, {0, 2}, {0, 3}, {1, 4}, {1, 5}, {3, 6}, {6, 7}}, Valor[] = {4,2, 3, -5,-1, 3, -2, 6}, A continuación se muestra el gráfico:
Salida: 6
Explicación:
La suma de todos los Nodes del 0.º nivel es 4. La
suma de todos los Nodes del 1.er nivel es 0.
La suma de todos los Nodes del 2.º nivel es 6.
Por lo tanto, la diferencia máxima absoluta de la suma de niveles = (6 – 0) = 6.Entrada: N = 10, Bordes[][2] = {{0, 1}, {0, 2}, {0, 3}, {1, 4}, {1, 5}, {3, 6}, {6, 7}, {6, 8}, {6, 9}}, Valor[] = {1, 2, -1, 3, 4, 5, 8, 6, 12, 7}, A continuación se muestra el gráfico :
Salida: 24
Enfoque: para encontrar la diferencia absoluta máxima de la suma de niveles, primero encuentre la suma de niveles máximos y la suma de niveles mínimos porque la diferencia absoluta de la suma de niveles máximos y la suma de niveles mínimos siempre nos da la diferencia absoluta máxima, es decir,
Diferencia absoluta máxima = abs (suma de nivel máximo – suma de nivel mínimo)
A continuación se muestran los pasos:
- Realice el BFS Traversal en el árbol N-ario .
- Mientras realiza el recorrido BFS, procese los Nodes de diferentes niveles por separado.
- Para cada nivel que se esté procesando, calcule la suma de los Nodes en el nivel y realice un seguimiento de la suma máxima y mínima del nivel.
- Después del recorrido anterior, encuentre la diferencia absoluta de la suma del nivel máximo y mínimo.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the maximum
// absolute difference of level sum
void maxAbsDiffLevelSum(int N, int M,
vector<int> cost,
int Edges[][2])
{
// Create the adjacency list
vector<int> adj[N];
for (int i = 0; i < M; i++) {
int u = Edges[i][0];
int v = Edges[i][1];
adj[u].push_back(v);
}
// Initialize value of maximum
// and minimum level sum
int maxSum = cost[0], minSum = cost[0];
// Do Level order traversal keeping
// track of nodes at every level
queue<int> q;
q.push(0);
while (!q.empty()) {
// Get the size of queue when
// the level order traversal
// for one level finishes
int count = q.size();
int sum = 0;
// Iterate for all the nodes
// in the queue currently
while (count--) {
// Dequeue an node from queue
int temp = q.front();
q.pop();
sum = sum + cost[temp];
// Enqueue the children of
// dequeued node
for (int i = 0;
i < adj[temp].size(); i++) {
q.push(adj[temp][i]);
}
}
// Update the maximum level
// sum value
maxSum = max(sum, maxSum);
// Update the minimum level
// sum value
minSum = min(sum, minSum);
}
// Return the result
cout << abs(maxSum - minSum);
}
// Driver Code
int main()
{
// Number of nodes and edges
int N = 10, M = 9;
// Edges of the N-ary tree
int Edges[][2] = { { 0, 1 }, { 0, 2 },
{ 0, 3 }, { 1, 4 },
{ 1, 5 }, { 3, 6 },
{ 6, 7 }, { 6, 8 },
{ 6, 9 } };
// Given cost
vector<int> cost = { 1, 2, -1, 3, 4,
5, 8, 6, 12, 7 };
// Function Call
maxAbsDiffLevelSum(N, M, cost, Edges);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to find the maximum
// absolute difference of level sum
static void maxAbsDiffLevelSum(int N, int M,
int []cost,
int Edges[][])
{
// Create the adjacency list
@SuppressWarnings("unchecked")
Vector<Integer> []adj = new Vector[N];
for(int i = 0; i < adj.length; i++)
adj[i] = new Vector<Integer>();
for(int i = 0; i < M; i++)
{
int u = Edges[i][0];
int v = Edges[i][1];
adj[u].add(v);
}
// Initialize value of maximum
// and minimum level sum
int maxSum = cost[0], minSum = cost[0];
// Do Level order traversal keeping
// track of nodes at every level
Queue<Integer> q = new LinkedList<Integer>();
q.add(0);
while (!q.isEmpty())
{
// Get the size of queue when
// the level order traversal
// for one level finishes
int count = q.size();
int sum = 0;
// Iterate for all the nodes
// in the queue currently
while (count-- > 0)
{
// Dequeue an node from queue
int temp = q.peek();
q.remove();
sum = sum + cost[temp];
// Enqueue the children of
// dequeued node
for(int i = 0;
i < adj[temp].size();
i++)
{
q.add(adj[temp].get(i));
}
}
// Update the maximum level
// sum value
maxSum = Math.max(sum, maxSum);
// Update the minimum level
// sum value
minSum = Math.min(sum, minSum);
}
// Return the result
System.out.print(Math.abs(maxSum - minSum));
}
// Driver Code
public static void main(String[] args)
{
// Number of nodes and edges
int N = 10, M = 9;
// Edges of the N-ary tree
int Edges[][] = { { 0, 1 }, { 0, 2 },
{ 0, 3 }, { 1, 4 },
{ 1, 5 }, { 3, 6 },
{ 6, 7 }, { 6, 8 },
{ 6, 9 } };
// Given cost
int []cost = { 1, 2, -1, 3, 4,
5, 8, 6, 12, 7 };
// Function call
maxAbsDiffLevelSum(N, M, cost, Edges);
}
}
// This code is contributed by Amit Katiyar
Python3
# Python3 program for the above approach from collections import deque # Function to find the maximum # absolute difference of level sum def maxAbsDiffLevelSum(N, M, cost, Edges): # Create the adjacency list adj = [[] for i in range(N)] for i in range(M): u = Edges[i][0] v = Edges[i][1] adj[u].append(v) # Initialize value of maximum # and minimum level sum maxSum = cost[0] minSum = cost[0] # Do Level order traversal keeping # track of nodes at every level q = deque() q.append(0) while len(q) > 0: # Get the size of queue when # the level order traversal # for one level finishes count = len(q) sum = 0 # Iterate for all the nodes # in the queue currently while (count): # Dequeue an node from queue temp = q.popleft() # q.pop() sum = sum + cost[temp] # Enqueue the children of # dequeued node for i in adj[temp]: q.append(i) count -= 1 # Update the maximum level # sum value maxSum = max(sum, maxSum) # Update the minimum level # sum value minSum = min(sum, minSum) # Return the result print(abs(maxSum - minSum)) # Driver Code if __name__ == '__main__': # Number of nodes and edges N = 10 M = 9 # Edges of the N-ary tree Edges = [ [ 0, 1 ], [ 0, 2 ], [ 0, 3 ], [ 1, 4 ], [ 1, 5 ], [ 3, 6 ], [ 6, 7 ], [ 6, 8 ], [ 6, 9 ] ] # Given cost cost = [ 1, 2, -1, 3, 4, 5, 8, 6, 12, 7 ] # Function call maxAbsDiffLevelSum(N, M, cost, Edges) # This code is contributed by mohit kumar 29
C#
// C# program for
// the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to find the maximum
// absolute difference of level sum
static void maxAbsDiffLevelSum(int N, int M,
int []cost,
int [,]Edges)
{
// Create the adjacency list
List<int> []adj = new List<int>[N];
for(int i = 0; i < adj.Length; i++)
adj[i] = new List<int>();
for(int i = 0; i < M; i++)
{
int u = Edges[i, 0];
int v = Edges[i, 1];
adj[u].Add(v);
}
// Initialize value of maximum
// and minimum level sum
int maxSum = cost[0], minSum = cost[0];
// Do Level order traversal keeping
// track of nodes at every level
Queue<int> q = new Queue<int>();
q.Enqueue(0);
while (q.Count!=0)
{
// Get the size of queue when
// the level order traversal
// for one level finishes
int count = q.Count;
int sum = 0;
// Iterate for all the nodes
// in the queue currently
while (count-- > 0)
{
// Dequeue an node from queue
int temp = q.Peek();
q.Dequeue();
sum = sum + cost[temp];
// Enqueue the children of
// dequeued node
for(int i = 0; i < adj[temp].Count; i++)
{
q.Enqueue(adj[temp][i]);
}
}
// Update the maximum level
// sum value
maxSum = Math.Max(sum, maxSum);
// Update the minimum level
// sum value
minSum = Math.Min(sum, minSum);
}
// Return the result
Console.Write(Math.Abs(maxSum - minSum));
}
// Driver Code
public static void Main(String[] args)
{
// Number of nodes and edges
int N = 10, M = 9;
// Edges of the N-ary tree
int [,]Edges = {{0, 1}, {0, 2},
{0, 3}, {1, 4},
{1, 5}, {3, 6},
{6, 7}, {6, 8},
{6, 9}};
// Given cost
int []cost = {1, 2, -1, 3, 4,
5, 8, 6, 12, 7};
// Function call
maxAbsDiffLevelSum(N, M, cost, Edges);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript implementation of the above approach
// Function to find the maximum
// absolute difference of level sum
function maxAbsDiffLevelSum(N, M, cost, Edges)
{
// Create the adjacency list
let adj = new Array(N);
for(let i = 0; i < adj.length; i++)
adj[i] = [];
for(let i = 0; i < M; i++)
{
let u = Edges[i][0];
let v = Edges[i][1];
adj[u].push(v);
}
// Initialize value of maximum
// and minimum level sum
let maxSum = cost[0], minSum = cost[0];
// Do Level order traversal keeping
// track of nodes at every level
let q = [];
q.push(0);
while (q.length!=0)
{
// Get the size of queue when
// the level order traversal
// for one level finishes
let count = q.length;
let sum = 0;
// Iterate for all the nodes
// in the queue currently
while (count-- > 0)
{
// Dequeue an node from queue
let temp = q[0];
q.shift();
sum = sum + cost[temp];
// Enqueue the children of
// dequeued node
for(let i = 0; i < adj[temp].length; i++)
{
q.push(adj[temp][i]);
}
}
// Update the maximum level
// sum value
maxSum = Math.max(sum, maxSum);
// Update the minimum level
// sum value
minSum = Math.min(sum, minSum);
}
// Return the result
document.write(Math.abs(maxSum - minSum));
}
// Number of nodes and edges
let N = 10, M = 9;
// Edges of the N-ary tree
let Edges = [[0, 1], [0, 2],
[0, 3], [1, 4],
[1, 5], [3, 6],
[6, 7], [6, 8],
[6, 9]];
// Given cost
let cost = [1, 2, -1, 3, 4, 5, 8, 6, 12, 7];
// Function call
maxAbsDiffLevelSum(N, M, cost, Edges);
</script>
Producción:
24
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por muskan_garg y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA