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>
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