Dado un árbol N-ario que consta de N Nodes numerados del 1 al N con raíz en el Node 1 , la tarea es asignar valores a cada Node del árbol de modo que la suma de los valores desde cualquier raíz hasta la ruta de la hoja que contiene al menos dos Nodes no es divisible por el número de Nodes a lo largo de ese camino.
Ejemplos:
Entrada: N = 11, bordes[][] = {{1, 2}, {1, 3}, {1, 4}, {1, 5}, {2, 6}, {2, 10}, { 10, 11}, {3, 7}, {4, 8}, {5, 9}}
Salida: 1 2 1 2 2 1 1
Explicación:
De acuerdo con la asignación de valores anterior, a continuación se muestran todos los caminos posibles desde la raíz hasta la hoja:
- Ruta 1 → 2 → 6, suma = 1 + 2 + 1 = 4, longitud = 3.
- Ruta 1 → 2 → 10 → 11, suma = 1 + 2 + 1 + 2 = 6, longitud = 4
- Ruta 1 → 3 → 7, suma = 1 + 2 + 1 = 4, longitud = 3.
- Ruta 1 → 4 → 8, suma = 1 + 2 + 1 = 4, longitud = 3.
- Ruta 1 → 5 → 9, suma = 1 + 2 + 1 = 4, longitud = 3.
De todos los caminos anteriores, ninguno de los caminos existe teniendo la suma de valores divisible por su longitud.
Entrada: N = 3, aristas = {{1, 2}, {2, 3}}
Salida: 1 2 1
Enfoque: El problema dado se puede resolver con base en la observación de que para cualquier camino de raíz a hoja con un número de Nodes de al menos 2 , digamos K si la suma de los valores a lo largo de este camino se encuentra entre K y 2*K exclusivo, entonces esa suma nunca puede ser divisible por K ya que cualquier número sobre el rango (K, 2*K) nunca es divisible por K. Por lo tanto, para K = 1 , asigne valores de Node de Nodes de nivel impar como 1 y el resto como 2 . Siga los pasos a continuación para resolver el problema:
- Inicialice una array , diga answer[] de tamaño N + 1 para almacenar los valores asignados a los Nodes.
- Inicialice una variable, diga K como 1 para asignar valores a cada Node.
- Inicialice una cola que se usa para realizar BFS Traversal en el árbol dado y empuje el Node con el valor 1 en la cola e inicialice el valor en los Nodes como 1 .
- Iterar hasta que la cola no esté vacía y realizar los siguientes pasos:
- Extraiga el Node frontal de la cola y, si el valor asignado al Node emergente es 1 , actualice el valor de K a 2 . De lo contrario, actualice K como 1 .
- Atraviese todos los Nodes secundarios del Node emergente actual y empuje el Node secundario en la cola y asigne el valor K al Node secundario.
- Después de completar los pasos anteriores, imprima los valores almacenados en la array answer[] como resultado.
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 assign values to nodes
// of the tree s.t. sum of values of
// nodes of path between any 2 nodes
// is not divisible by length of path
void assignValues(int Edges[][2], int n)
{
// Stores the adjacency list
vector <int> tree[n + 1];
// Create a adjacency list
for(int i = 0; i < n - 1; i++) {
int u = Edges[i][0];
int v = Edges[i][1];
tree[u].push_back(v);
tree[v].push_back(u);
}
// Stores whether node is
// visited or not
vector <bool> visited(n + 1, false);
// Stores the node values
vector <int> answer(n + 1);
// Variable used to assign values to
// the nodes alternatively to the
// parent child
int K = 1;
// Declare a queue
queue <int> q;
// Push the 1st node
q.push(1);
// Assign K value to this node
answer[1] = K;
while (!q.empty()) {
// Dequeue the node
int node = q.front();
q.pop();
// Mark it as visited
visited[node] = true;
// Upgrade the value of K
K = ((answer[node] == 1) ? 2 : 1);
// Assign K to the child nodes
for (auto child : tree[node]) {
// If the child is unvisited
if (!visited[child]) {
// Enqueue the child
q.push(child);
// Assign K to the child
answer[child] = K;
}
}
}
// Print the value assigned to
// the nodes
for (int i = 1; i <= n; i++) {
cout << answer[i] << " ";
}
}
// Driver Code
int main()
{
int N = 11;
int Edges[][2] = {{1, 2}, {1, 3}, {1, 4},
{1, 5}, {2, 6}, {2, 10},
{10, 11}, {3, 7}, {4, 8},
{5, 9}};
// Function Call
assignValues(Edges, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to assign values to nodes
// of the tree s.t. sum of values of
// nodes of path between any 2 nodes
// is not divisible by length of path
static void assignValues(int Edges[][], int n)
{
// Stores the adjacency list
ArrayList<ArrayList<Integer>> tree = new ArrayList<>();
for(int i = 0; i < n + 1; i++)
tree.add(new ArrayList<>());
// Create a adjacency list
for(int i = 0; i < n - 1; i++)
{
int u = Edges[i][0];
int v = Edges[i][1];
tree.get(u).add(v);
tree.get(v).add(u);
}
// Stores whether node is
// visited or not
boolean[] visited = new boolean[n + 1];
// Stores the node values
int[] answer = new int[n + 1];
// Variable used to assign values to
// the nodes alternatively to the
// parent child
int K = 1;
// Declare a queue
Queue<Integer> q = new LinkedList<>();
// Push the 1st node
q.add(1);
// Assign K value to this node
answer[1] = K;
while (!q.isEmpty())
{
// Dequeue the node
int node = q.peek();
q.poll();
// Mark it as visited
visited[node] = true;
// Upgrade the value of K
K = ((answer[node] == 1) ? 2 : 1);
// Assign K to the child nodes
for(Integer child : tree.get(node))
{
// If the child is unvisited
if (!visited[child])
{
// Enqueue the child
q.add(child);
// Assign K to the child
answer[child] = K;
}
}
}
// Print the value assigned to
// the nodes
for(int i = 1; i <= n; i++)
{
System.out.print(answer[i] + " ");
}
}
// Driver code
public static void main(String[] args)
{
int N = 11;
int Edges[][] = { { 1, 2 }, { 1, 3 },
{ 1, 4 }, { 1, 5 },
{ 2, 6 }, { 2, 10 },
{ 10, 11 }, { 3, 7 },
{ 4, 8 }, { 5, 9 } };
// Function Call
assignValues(Edges, N);
}
}
// This code is contributed by offbeat
Python3
# Python3 program for the above approach from collections import deque # Function to assign values to nodes # of the tree s.t. sum of values of # nodes of path between any 2 nodes # is not divisible by length of path def assignValues(Edges, n): # Stores the adjacency list tree = [[] for i in range(n + 1)] # Create a adjacency list for i in range(n - 1): u = Edges[i][0] v = Edges[i][1] tree[u].append(v) tree[v].append(u) # Stores whether any node is # visited or not visited = [False]*(n+1) # Stores the node values answer = [0]*(n + 1) # Variable used to assign values to # the nodes alternatively to the # parent child K = 1 # Declare a queue q = deque() # Push the 1st node q.append(1) # Assign K value to this node answer[1] = K while (len(q) > 0): # Dequeue the node node = q.popleft() # q.pop() # Mark it as visited visited[node] = True # Upgrade the value of K K = 2 if (answer[node] == 1) else 1 # Assign K to the child nodes for child in tree[node]: # If the child is unvisited if (not visited[child]): # Enqueue the child q.append(child) # Assign K to the child answer[child] = K # Print the value assigned to # the nodes for i in range(1, n + 1): print(answer[i],end=" ") # Driver Code if __name__ == '__main__': N = 7 Edges = [ [ 1, 2 ], [ 4, 6 ], [ 3, 5 ], [ 1, 4 ], [ 7, 5 ], [ 5, 1 ] ] # Function Call assignValues(Edges, N) # This code is contributed by mohit kumar 29.
C#
// C# program for the above approach
using System;
using System.Collections;
using System.Collections.Generic;
public class GFG{
// Function to assign values to nodes
// of the tree s.t. sum of values of
// nodes of path between any 2 nodes
// is not divisible by length of path
static void assignValues(int[, ] Edges, int n)
{
// Stores the adjacency list
LinkedList<int>[] tree = new LinkedList<int>[n+1];
for(int i = 0; i < n + 1; i++)
tree[i] = new LinkedList<int>();
// Create a adjacency list
for(int i = 0; i < n - 1; i++)
{
int u = Edges[i, 0];
int v = Edges[i, 1];
tree[u].AddLast(v);
tree[v].AddLast(u);
}
// Stores whether node is
// visited or not
bool[] visited = new bool[n + 1];
// Stores the node values
int[] answer = new int[n + 1];
// Variable used to assign values to
// the nodes alternatively to the
// parent child
int K = 1;
// Declare a queue
Queue q = new Queue();
// Push the 1st node
q.Enqueue(1);
// Assign K value to this node
answer[1] = K;
while (q.Count > 0)
{
// Dequeue the node
int node = (int)q.Peek();
q.Dequeue();
// Mark it as visited
visited[node] = true;
// Upgrade the value of K
K = ((answer[node] == 1) ? 2 : 1);
// Assign K to the child nodes
foreach (var child in tree[node])
{
// If the child is unvisited
if (!visited[child])
{
// Enqueue the child
q.Enqueue(child);
// Assign K to the child
answer[child] = K;
}
}
}
// Print the value assigned to
// the nodes
for(int i = 1; i <= n; i++)
{
Console.Write(answer[i] + " ");
}
}
// Driver code
static public void Main (){
int N = 11;
int[, ] Edges = { { 1, 2 }, { 1, 3 },
{ 1, 4 }, { 1, 5 },
{ 2, 6 }, { 2, 10 },
{ 10, 11 }, { 3, 7 },
{ 4, 8 }, { 5, 9 } };
// Function Call
assignValues(Edges, N);
}
}
// This code is contributed by Dharanendra L V.
Javascript
<script>
// Javascript program for the above approach
// Function to assign values to nodes
// of the tree s.t. sum of values of
// nodes of path between any 2 nodes
// is not divisible by length of path
function assignValues(Edges, n)
{
// Stores the adjacency list
var tree = Array.from(Array(n+1), ()=> Array());
// Create a adjacency list
for(var i = 0; i < n - 1; i++) {
var u = Edges[i][0];
var v = Edges[i][1];
tree[u].push(v);
tree[v].push(u);
}
// Stores whether node is
// visited or not
var visited = Array(n + 1).fill(false);
// Stores the node values
var answer = Array(n + 1);
// Variable used to assign values to
// the nodes alternatively to the
// parent child
var K = 1;
// Declare a queue
var q = [];
// Push the 1st node
q.push(1);
// Assign K value to this node
answer[1] = K;
while (q.length!=0) {
// Dequeue the node
var node = q[0];
q.shift();
// Mark it as visited
visited[node] = true;
// Upgrade the value of K
K = ((answer[node] == 1) ? 2 : 1);
// Assign K to the child nodes
tree[node].forEach(child => {
// If the child is unvisited
if (!visited[child]) {
// Enqueue the child
q.push(child);
// Assign K to the child
answer[child] = K;
}
});
}
// Print the value assigned to
// the nodes
for (var i = 1; i <= n; i++) {
document.write( answer[i] + " ");
}
}
// Driver Code
var N = 11;
var Edges = [[1, 2], [1, 3], [1, 4],
[1, 5], [2, 6], [2, 10],
[10, 11], [3, 7], [4, 8],
[5, 9]];
// Function Call
assignValues(Edges, N);
</script>
Producción:
1 2 2 2 2 1 1 1 1 1 2
Complejidad temporal: O(N), donde N es el número total de Nodes del árbol.
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por ramandeep8421 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA