Cuente el número de Nodes en un gráfico cuya suma de vecinos es como máximo K

Dada una raíz de gráfico y un valor K, la tarea es encontrar el número de Nodes en el gráfico cuya suma de vecinos es menor que K.

Ejemplo:

Entrada: raíz = 8 K = 14
                   / \
           2—3 7—3
               / \ \
            5 6 0
             \ \ / \
             1 2 6 9
Salida: 10
Explicación: Los Nodes con suma de vecinos menor que 14 son los Nodes con valor 8, 7, 6, 9, 3 (más a la derecha), 2, 5, 1, 6, 2

Entrada: raíz =2 K = 5
                   / \
                3 1
              / \
            5 6
Salida: 3

 

Enfoque: El problema dado se puede resolver utilizando la búsqueda en profundidad en el gráfico. La idea es usar la recursividad y visitar cada Node para verificar que la suma de su Node vecino sea menor que K. Se pueden seguir los pasos a continuación para resolver el problema:

  • Use la recursividad para aplicar la búsqueda en profundidad  en el gráfico y use un hashset para almacenar los Nodes visitados del gráfico
  • En cada Node iterar a través de los vecinos de ese Node y agregar su suma
    • Si la suma es mayor que K entonces incremente el conteo
  • Devuelve el conteo como resultado.

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

C++

// C++ code for the above approach
#include <bits/stdc++.h>
using namespace std;
 
class Node
{
public:
    vector<Node *> neighbors;
    int val;
    Node(int v)
    {
        val = v;
        neighbors = {};
    }
};
// Depth first search function to visit
// every node of the graph and check if
// sum of neighbor nodes is less than K
void dfs(
    Node *root,
    set<Node *> &visited,
    vector<int> &count, int K)
{
 
    // If the current node is
    // already visited then return
    if (visited.find(root) != visited.end())
        return;
 
    // Mark the current node as visited
    visited.insert(root);
 
    // Initialize a variable sum to
    // calculate sum of neighbors
    int sum = 0;
 
    // Iterate through all neighbors
    for (Node *n : root->neighbors)
    {
        sum += n->val;
    }
 
    // If sum is less than K then
    // increment count by 1
    if (sum < K)
        count[0] = count[0] + 1;
 
    for (Node *n : root->neighbors)
    {
 
        // Visit the neighbor nodes
        dfs(n, visited, count, K);
    }
}
 
// Function to find the number of nodes
// in the graph with sum less than K
int nodeSumLessThanK(
    Node *root, int K)
{
 
    // Initialize the variable count
    // to count the answer
    vector<int> count(1, 0);
    // Initialize a HashSet to
    // store the visited nodes
    set<Node *> visited;
 
    // Apply DFS on the graph
    dfs(root, visited, count, K);
 
    // Return the answer stored in count
    return count[0];
}
 
// Driver code
int main()
{
 
    // Initialize the graph
    Node *root = new Node(2);
    root->neighbors.push_back(new Node(3));
    root->neighbors.push_back(new Node(1));
    root->neighbors[0]->neighbors.push_back(new Node(5));
    root->neighbors[1]->neighbors.push_back(new Node(6));
    int K = 5;
 
    // Call the function
    // and print the result
    cout << (nodeSumLessThanK(root, K));
    return 0;
}
 
// This code is contributed by Potta Lokesh

Java

// Java implementation for the above approach
 
import java.io.*;
import java.util.*;
 
class GFG {
 
    static class Node {
 
        List<Node> neighbors;
        int val;
        public Node(int val)
        {
            this.val = val;
            neighbors = new ArrayList<>();
        }
    }
 
    // Function to find the number of nodes
    // in the graph with sum less than K
    public static int nodeSumLessThanK(
        Node root, int K)
    {
 
        // Initialize the variable count
        // to count the answer
        int[] count = new int[1];
 
        // Initialize a HashSet to
        // store the visited nodes
        Set<Node> visited = new HashSet<>();
 
        // Apply DFS on the graph
        dfs(root, visited, count, K);
 
        // Return the answer stored in count
        return count[0];
    }
 
    // Depth first search function to visit
    // every node of the graph and check if
    // sum of neighbor nodes is less than K
    public static void dfs(
        Node root,
        Set<Node> visited,
        int[] count, int K)
    {
 
        // If the current node is
        // already visited then return
        if (visited.contains(root))
            return;
 
        // Mark the current node as visited
        visited.add(root);
 
        // Initialize a variable sum to
        // calculate sum of neighbors
        int sum = 0;
 
        // Iterate through all neighbors
        for (Node n : root.neighbors) {
            sum += n.val;
        }
 
        // If sum is less than K then
        // increment count by 1
        if (sum < K)
            count[0]++;
 
        for (Node n : root.neighbors) {
 
            // Visit the neighbor nodes
            dfs(n, visited, count, K);
        }
    }
 
    // Driver code
    public static void main(String[] args)
    {
 
        // Initialize the graph
        Node root = new Node(2);
        root.neighbors.add(new Node(3));
        root.neighbors.add(new Node(1));
        root.neighbors.get(0)
            .neighbors.add(new Node(5));
        root.neighbors.get(1)
            .neighbors.add(new Node(6));
        int K = 5;
 
        // Call the function
        // and print the result
        System.out.println(
            nodeSumLessThanK(root, K));
    }
}

C#

// C# implementation for the above approach
using System;
using System.Collections.Generic;
 
public class GFG {
 
    class Node {
 
        public List<Node> neighbors;
        public int val;
        public Node(int val)
        {
            this.val = val;
            neighbors = new List<Node>();
        }
    }
 
    // Function to find the number of nodes
    // in the graph with sum less than K
    static int nodeSumLessThanK(
        Node root, int K)
    {
 
        // Initialize the variable count
        // to count the answer
        int[] count = new int[1];
 
        // Initialize a HashSet to
        // store the visited nodes
        HashSet<Node> visited = new HashSet<Node>();
 
        // Apply DFS on the graph
        dfs(root, visited, count, K);
 
        // Return the answer stored in count
        return count[0];
    }
 
    // Depth first search function to visit
    // every node of the graph and check if
    // sum of neighbor nodes is less than K
    static void dfs(
        Node root,
        HashSet<Node> visited,
        int[] count, int K)
    {
 
        // If the current node is
        // already visited then return
        if (visited.Contains(root))
            return;
 
        // Mark the current node as visited
        visited.Add(root);
 
        // Initialize a variable sum to
        // calculate sum of neighbors
        int sum = 0;
 
        // Iterate through all neighbors
        foreach (Node n in root.neighbors) {
            sum += n.val;
        }
 
        // If sum is less than K then
        // increment count by 1
        if (sum < K)
            count[0]++;
 
        foreach (Node n in root.neighbors) {
 
            // Visit the neighbor nodes
            dfs(n, visited, count, K);
        }
    }
 
    // Driver code
    public static void Main(String[] args)
    {
 
        // Initialize the graph
        Node root = new Node(2);
        root.neighbors.Add(new Node(3));
        root.neighbors.Add(new Node(1));
        root.neighbors[0]
            .neighbors.Add(new Node(5));
        root.neighbors[1]
            .neighbors.Add(new Node(6));
        int K = 5;
 
        // Call the function
        // and print the result
        Console.WriteLine(
            nodeSumLessThanK(root, K));
    }
}
 
// This code is contributed by shikhasingrajput

Javascript

<script>
// Javascript code for the above approach
 
class Node {
  constructor(v) {
    this.val = v;
    this.neighbors = [];
  }
};
// Depth first search function to visit
// every node of the graph and check if
// sum of neighbor nodes is less than K
function dfs(root, visited, count, K) {
 
  // If the current node is
  // already visited then return
  if (visited.has(root))
    return;
 
  // Mark the current node as visited
  visited.add(root);
 
  // Initialize a variable sum to
  // calculate sum of neighbors
  let sum = 0;
 
  // Iterate through all neighbors
  for (let n of root.neighbors) {
    sum += n.val;
  }
 
  // If sum is less than K then
  // increment count by 1
  if (sum < K)
    count[0] = count[0] + 1;
 
  for (let n of root.neighbors) {
 
    // Visit the neighbor nodes
    dfs(n, visited, count, K);
  }
}
 
// Function to find the number of nodes
// in the graph with sum less than K
function nodeSumLessThanK(root, K) {
 
  // Initialize the variable count
  // to count the answer
  let count = new Array(1).fill(0);
  // Initialize a HashSet to
  // store the visited nodes
  let visited = new Set();
 
  // Apply DFS on the graph
  dfs(root, visited, count, K);
 
  // Return the answer stored in count
  return count[0];
}
 
// Driver code
 
 
// Initialize the graph
let root = new Node(2);
root.neighbors.push(new Node(3));
root.neighbors.push(new Node(1));
root.neighbors[0].neighbors.push(new Node(5));
root.neighbors[1].neighbors.push(new Node(6));
let K = 5;
 
// Call the function
// and print the result
document.write(nodeSumLessThanK(root, K));
 
// This code is contributed by gfgking.
</script>
Producción

3

Complejidad Temporal: O(V + E), donde V es el número de vértices y E es el número de aristas en el grafo
Espacio Auxiliar: O(V)

Publicación traducida automáticamente

Artículo escrito por rahulkr8 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *