Dada una array de pesos[] que consta de N enteros positivos, donde pesos[i] denota el peso del i -ésimo Node, la tarea es construir un árbol N-ario tal que no haya dos Nodes conectados directamente que tengan el mismo peso. Si es posible hacer un árbol de este tipo, imprima «Sí» junto con sus bordes. De lo contrario, escriba “No” .
Ejemplos:
Entrada: pesos[] = {1 2 1 2 5}
Salida:
Sí
1 2
1 4
1 5
2 3
Explicación:
Índice: 1 2 3 4 5
Peso: 1 2 1 2 5
El árbol construido se muestra en el siguiente diagrama:
Entrada: pesos[] = {1 1 1}
Salida: No
Explicación: Dado que todos los pesos ya son iguales, no se puede construir tal árbol.
Enfoque: La idea para resolver este problema es verificar primero si todos los Nodes están asignados con el mismo peso o no. Si se determina que es cierto, no se puede construir el árbol requerido. De lo contrario, se puede construir un árbol de este tipo. Por lo tanto , recorra los pesos de la array [] y verifique si todos los valores son iguales o no. Si es cierto, escriba “ No” . De lo contrario, imprima «Sí» y construya un árbol siguiendo los siguientes pasos:
- Tome cualquier Node y conviértalo en el Node raíz .
- Ahora, conecte todos los demás Nodes con pesos distintos al de la raíz al Node raíz. Ahora los Nodes restantes son los Nodes que tienen un valor igual al Node raíz.
- Elija cualquier Node secundario del Node raíz y conecte todos los Nodes restantes a ellos. Por lo tanto, no existe borde directo entre Nodes del mismo peso.
- Para verificar qué Nodes aún no se han incluido, realice un seguimiento de los Nodes visitados utilizando una array auxiliar visited[] . Si se visita un Node, una un Node con él, pero no una el Node visitado con otro Node, ya que es posible unir un Node no visitado con un Node visitado, pero no viceversa.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
// Keep track of visited nodes
int visited[N];
// Function to construct a tree such
// that there are no two adjacent
// nodes with the same weight
void construct_tree(int weights[], int n)
{
int minimum = *min_element(weights, weights + n);
int maximum = *max_element(weights, weights + n);
// If minimum and maximum
// elements are equal, i.e.
// array contains one distinct element
if (minimum == maximum) {
// Tree cannot be constructed
cout << "No";
return;
}
// Otherwise
else {
// Tree can be constructed
cout << "Yes" << endl;
}
// Find the edges below
// Choose weights[0] as root
int root = weights[0];
// First Node is visited
visited[1] = 1;
// Traverse the array
for (int i = 0; i < n; i++) {
// If current element has the
// same weight as root and if
// the node is visited, then
// do not make an edge
// Otherwise, make an edge
if (weights[i] != root
&& visited[i + 1] == 0) {
cout << 1 << " "
<< i + 1 << " "
<< endl;
// Mark this node as visited
visited[i + 1] = 1;
}
}
// Find a weight not same as the
// root & make edges with that node
int notroot = 0;
for (int i = 0; i < n; i++) {
if (weights[i] != root) {
notroot = i + 1;
break;
}
}
// Join non-roots with remaining nodes
for (int i = 0; i < n; i++) {
// Check if current node's weight
// is same as root node's weight
// and if it is not visited or not
if (weights[i] == root
&& visited[i + 1] == 0) {
cout << notroot << " "
<< i + 1 << endl;
visited[i + 1] = 1;
}
}
}
// Driver Code
int main()
{
int weights[] = { 1, 2, 1, 2, 5 };
int N = sizeof(weights) / sizeof(weights[0]);
// Function Call
construct_tree(weights, N);
}
Java
// Java program to implement
// the above approach
import java.lang.*;
import java.io.*;
import java.util.*;
class GFG{
static int N = 100000 + 5;
// Keep track of visited nodes
static int visited[] = new int[N];
// Function to construct a tree such
// that there are no two adjacent
// nodes with the same weight
static void construct_tree(int weights[], int n)
{
int minimum = Arrays.stream(weights).min().getAsInt();
int maximum = Arrays.stream(weights).max().getAsInt();
// If minimum and maximum
// elements are equal, i.e.
// array contains one distinct element
if (minimum == maximum)
{
// Tree cannot be constructed
System.out.println("No");
return;
}
// Otherwise
else
{
// Tree can be constructed
System.out.println("Yes");
}
// Find the edges below
// Choose weights[0] as root
int root = weights[0];
// First Node is visited
visited[1] = 1;
// Traverse the array
for(int i = 0; i < n; i++)
{
// If current element has the
// same weight as root and if
// the node is visited, then
// do not make an edge
// Otherwise, make an edge
if (weights[i] != root &&
visited[i + 1] == 0)
{
System.out.println(1 + " " +
(i + 1) + " ");
// Mark this node as visited
visited[i + 1] = 1;
}
}
// Find a weight not same as the
// root & make edges with that node
int notroot = 0;
for(int i = 0; i < n; i++)
{
if (weights[i] != root)
{
notroot = i + 1;
break;
}
}
// Join non-roots with remaining nodes
for(int i = 0; i < n; i++)
{
// Check if current node's weight
// is same as root node's weight
// and if it is not visited or not
if (weights[i] == root &&
visited[i + 1] == 0)
{
System.out.println(notroot + " " +
(i + 1));
visited[i + 1] = 1;
}
}
}
// Driver Code
public static void main(String[] args)
{
int weights[] = { 1, 2, 1, 2, 5 };
int N = weights.length;
// Function Call
construct_tree(weights, N);
}
}
// This code is contributed by sanjoy_62
Python3
# Python3 program to implement
# the above approach
N = 10**5 + 5
#Keep track of visited nodes
visited=[0]*N
#Function to construct a tree such
#that there are no two adjacent
#nodes with the same weight
def construct_tree(weights, n):
minimum = min(weights)
maximum = max(weights)
#If minimum and maximum
#elements are equal, i.e.
#array contains one distinct element
if (minimum == maximum):
#Tree cannot be constructed
print("No")
return
#Otherwise
else:
print("Yes")
#Find the edges below
#Choose weights[0] as root
root = weights[0]
#First Node is visited
visited[1] = 1
#Traverse the array
for i in range(n):
#If current element has the
#same weight as root and if
#the node is visited, then
#do not make an edge
#Otherwise, make an edge
if (weights[i] != root
and visited[i + 1] == 0):
print(1,i+1)
#Mark this node as visited
visited[i + 1] = 1
#Find a weight not same as the
#root & make edges with that node
notroot = 0
for i in range(n):
if (weights[i] != root):
notroot = i + 1
break
#Join non-roots with remaining nodes
for i in range(n):
#Check if current node's weight
#is same as root node's weight
#and if it is not visited or not
if (weights[i] == root
and visited[i + 1] == 0):
print(notroot,i + 1)
visited[i + 1] = 1
#Driver Code
if __name__ == '__main__':
weights=[1, 2, 1, 2, 5]
N = len(weights)
#Function Call
construct_tree(weights, N)
C#
// C# program to implement
// the above approach
using System;
using System.Linq;
class GFG{
static int N = 100000 + 5;
// Keep track of visited nodes
static int[] visited = new int[N];
// Function to construct a tree such
// that there are no two adjacent
// nodes with the same weight
static void construct_tree(int[] weights, int n)
{
int minimum = weights.Min();
int maximum = weights.Max();
// If minimum and maximum
// elements are equal, i.e.
// array contains one distinct element
if (minimum == maximum)
{
// Tree cannot be constructed
Console.WriteLine("No");
return;
}
// Otherwise
else
{
// Tree can be constructed
Console.WriteLine("Yes");
}
// Find the edges below
// Choose weights[0] as root
int root = weights[0];
// First Node is visited
visited[1] = 1;
// Traverse the array
for(int i = 0; i < n; i++)
{
// If current element has the
// same weight as root and if
// the node is visited, then
// do not make an edge
// Otherwise, make an edge
if (weights[i] != root &&
visited[i + 1] == 0)
{
Console.WriteLine(1 + " " + (i + 1) + " ");
// Mark this node as visited
visited[i + 1] = 1;
}
}
// Find a weight not same as the
// root & make edges with that node
int notroot = 0;
for(int i = 0; i < n; i++)
{
if (weights[i] != root)
{
notroot = i + 1;
break;
}
}
// Join non-roots with remaining nodes
for(int i = 0; i < n; i++)
{
// Check if current node's weight
// is same as root node's weight
// and if it is not visited or not
if (weights[i] == root &&
visited[i + 1] == 0)
{
Console.WriteLine(notroot + " " +
(i + 1));
visited[i + 1] = 1;
}
}
}
// Driver Code
public static void Main()
{
int[] weights = { 1, 2, 1, 2, 5 };
int N = weights.Length;
// Function Call
construct_tree(weights, N);
}
}
// This code is contributed by code_hunt.
Javascript
<script>
// Javascript program to implement
// the above approach
let N = 100000 + 5;
// Keep track of visited nodes
let visited = new Array(N);
visited.fill(0);
// Function to construct a tree such
// that there are no two adjacent
// nodes with the same weight
function construct_tree(weights, n)
{
let minimum = Number.MAX_VALUE;
let maximum = Number.MIN_VALUE;
for(let i = 0; i < weights.length; i++)
{
minimum = Math.min(minimum, weights[i]);
maximum = Math.max(maximum, weights[i]);
}
// If minimum and maximum
// elements are equal, i.e.
// array contains one distinct element
if (minimum == maximum)
{
// Tree cannot be constructed
document.write("No");
return;
}
// Otherwise
else
{
// Tree can be constructed
document.write("Yes" + "</br>");
}
// Find the edges below
// Choose weights[0] as root
let root = weights[0];
// First Node is visited
visited[1] = 1;
// Traverse the array
for(let i = 0; i < n; i++)
{
// If current element has the
// same weight as root and if
// the node is visited, then
// do not make an edge
// Otherwise, make an edge
if (weights[i] != root &&
visited[i + 1] == 0)
{
document.write(1 + " " +
(i + 1) + "</br>");
// Mark this node as visited
visited[i + 1] = 1;
}
}
// Find a weight not same as the
// root & make edges with that node
let notroot = 0;
for(let i = 0; i < n; i++)
{
if (weights[i] != root)
{
notroot = i + 1;
break;
}
}
// Join non-roots with remaining nodes
for(let i = 0; i < n; i++)
{
// Check if current node's weight
// is same as root node's weight
// and if it is not visited or not
if (weights[i] == root &&
visited[i + 1] == 0)
{
document.write(notroot + " " +
(i + 1) + "</br>");
visited[i + 1] = 1;
}
}
}
// Driver code
let weights = [ 1, 2, 1, 2, 5 ];
let n = weights.length;
// Function Call
construct_tree(weights, n);
// This code is contributed by divyeshrabadiya07
</script>
Producción:
Yes 1 2 1 4 1 5 2 3
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por sameerbamanha y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA