Construya un árbol N-ario que no tenga un par de Nodes adyacentes con el mismo peso a partir de pesos dados

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:

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

Deja una respuesta

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