Imprime el grado de cada Node de la secuencia de Prufer dada

Dada una secuencia de Prufer , la tarea es encontrar los grados de todos los Nodes del árbol formado por la secuencia de Prufer.
Ejemplos: 
 

Input: arr[] = {4, 1, 3, 4} 
Output: 2 1 2 3 1 1

The tree is:
2----4----3----1----5
     |
     6 

Input: arr[] = {1, 2, 2} 
Output: 2 3 1 1 1

Un enfoque simple es crear el árbol usando la secuencia de Prufer y luego encontrar el grado de todos los Nodes. 
Enfoque eficiente: cree una array de grado [] de tamaño 2 más que la longitud de la secuencia de prufer, ya que la longitud de la secuencia de prufer es N – 2 si N es el número de Nodes. Inicialmente, llene la array de grados con 1 . Iterar en la secuencia de Prufer y aumentar la frecuencia en la tabla de grados para cada elemento. Este método funciona porque la frecuencia de un Node en la secuencia de Prufer es uno menos que el grado en el árbol. 
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to print the degrees of every
// node in the tree made by
// the given Prufer sequence
void printDegree(int prufer[], int n)
{
    int node = n + 2;
 
    // Hash-table to mark the
    // degree of every node
    int degree[n + 2 + 1];
 
    // Initially let all the degrees be 1
    for (int i = 1; i <= node; i++)
        degree[i] = 1;
 
    // Increase the count of the degree
    for (int i = 0; i < n; i++)
        degree[prufer[i]]++;
 
    // Print the degree of every node
    for (int i = 1; i <= node; i++) {
        cout << degree[i] << " ";
    }
}
 
// Driver code
int main()
{
    int a[] = { 4, 1, 3, 4 };
    int n = sizeof(a) / sizeof(a[0]);
    printDegree(a, n);
 
    return 0;
}

// Java implementation of the approach
import java.util.*;
 
class GFG
{
 
    // Function to print the degrees of every
    // node in the tree made by
    // the given Prufer sequence
    static void printDegree(int prufer[], int n)
    {
        int node = n + 2;
 
        // Hash-table to mark the
        // degree of every node
        int[] degree = new int[n + 2 + 1];
 
        // Initially let all the degrees be 1
        for (int i = 1; i <= node; i++)
        {
            degree[i] = 1;
        }
 
        // Increase the count of the degree
        for (int i = 0; i < n; i++)
        {
            degree[prufer[i]]++;
        }
 
        // Print the degree of every node
        for (int i = 1; i <= node; i++)
        {
            System.out.print(degree[i] + " ");
        }
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int a[] = {4, 1, 3, 4};
        int n = a.length;
        printDegree(a, n);
    }
}
 
/* This code contributed by PrinciRaj1992 */

# Python3 implementation of the approach
 
# Function to print the degrees of
# every node in the tree made by
# the given Prufer sequence
def printDegree(prufer, n):
  
    node = n + 2
 
    # Hash-table to mark the
    # degree of every node
    degree = [1] * (n + 2 + 1)
 
    # Increase the count of the degree
    for i in range(0, n):
        degree[prufer[i]] += 1
 
    # Print the degree of every node
    for i in range(1, node+1): 
        print(degree[i], end = " ")
      
# Driver code
if __name__ == "__main__":
  
    a = [4, 1, 3, 4]
    n = len(a)
    printDegree(a, n)
 
# This code is contributed by Rituraj Jain

// C# implementation of the approach
using System;
     
class GFG
{
 
// Function to print the degrees of every
// node in the tree made by
// the given Prufer sequence
static void printDegree(int []prufer, int n)
{
    int node = n + 2;
 
    // Hash-table to mark the
    // degree of every node
    int[] degree = new int[n + 2 + 1];
 
    // Initially let all the degrees be 1
    for (int i = 1; i <= node; i++)
    {
        degree[i] = 1;
    }
 
    // Increase the count of the degree
    for (int i = 0; i < n; i++)
    {
        degree[prufer[i]]++;
    }
 
    // Print the degree of every node
    for (int i = 1; i <= node; i++)
    {
        Console.Write(degree[i] + " ");
    }
}
 
// Driver code
public static void Main(String[] args)
{
    int []a = {4, 1, 3, 4};
    int n = a.Length;
    printDegree(a, n);
}
}
 
// This code is contributed by 29AjayKumar

<script>
 
// JavaScript implementation of the approach
 
    // Function to print the degrees of every
    // node in the tree made by
    // the given Prufer sequence
    function printDegree(prufer , n)
    {
        var node = n + 2;
 
        // Hash-table to mark the
        // degree of every node
        var degree = Array(n + 2 + 1).fill(0);
 
        // Initially let all the degrees be 1
        for (i = 1; i <= node; i++) {
            degree[i] = 1;
        }
 
        // Increase the count of the degree
        for (i = 0; i < n; i++) {
            degree[prufer[i]]++;
        }
 
        // Print the degree of every node
        for (i = 1; i <= node; i++) {
            document.write(degree[i] + " ");
        }
    }
 
    // Driver code
     
        var a = [ 4, 1, 3, 4 ];
        var n = a.length;
        printDegree(a, n);
 
// This code contributed by Rajput-Ji
 
</script>

2 1 2 3 1 1

Complejidad de tiempo: O (N), ya que estamos usando un bucle para atravesar N veces. Donde N es el número de elementos de la array.

Espacio auxiliar: O (N), ya que estamos usando una array de grados de espacio adicional.