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, 2Entrada: 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)