Рубрики

Вывести степень каждого узла из данной последовательности Prufer

Учитывая последовательность прюферова , задача состоит в том, чтобы найти степени все узлы дерева , сделанные последовательностями прюферова.

Примеры:

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

Простой подход состоит в том, чтобы создать дерево, используя последовательность Prufer, а затем найти степень всех узлов.

Эффективный подход: создайте массив градусов [] размером 2 больше, чем длина последовательности prufer, поскольку длина последовательности prufer равна N — 2, если N — число узлов. Сначала заполните массив градусов 1 . Повторяйте последовательность Prufer и увеличивайте частоту в таблице степеней для каждого элемента. Этот метод работает, потому что частота узла в последовательности Prufer на единицу меньше, чем степень в дереве.

Ниже приведена реализация вышеуказанного подхода:

C ++

// C ++ реализация подхода
#include <bits/stdc++.h>

using namespace std;

  
// Функция для печати градусов каждого
// узел в дереве сделан
// заданная последовательность Prufer

void printDegree(int prufer[], int n)

{

    int node = n + 2;

  

    // Хеш-таблица для пометки

    // степень каждого узла

    int degree[n + 2 + 1];

  

    // Первоначально позвольте всем степеням быть 1

    for (int i = 1; i <= node; i++)

        degree[i] = 1;

  

    // Увеличить счет степени

    for (int i = 0; i < n; i++)

        degree[prufer[i]]++;

  

    // Распечатать степень каждого узла

    for (int i = 1; i <= node; i++) {

        cout << degree[i] << " ";

    }

}

  
// Код драйвера

int main()

{

    int a[] = { 4, 1, 3, 4 };

    int n = sizeof(a) / sizeof(a[0]);

    printDegree(a, n);

  

    return 0;

}

Джава

// Java реализация подхода

import java.util.*;

  

class GFG 

{

  

    // Функция для печати градусов каждого

    // узел в дереве сделан

    // заданная последовательность Prufer

    static void printDegree(int prufer[], int n) 

    {

        int node = n + 2;

  

        // Хеш-таблица для пометки

        // степень каждого узла

        int[] degree = new int[n + 2 + 1];

  

        // Первоначально позвольте всем степеням быть 1

        for (int i = 1; i <= node; i++)

        {

            degree[i] = 1;

        }

  

        // Увеличить счет степени

        for (int i = 0; i < n; i++) 

        {

            degree[prufer[i]]++;

        }

  

        // Распечатать степень каждого узла

        for (int i = 1; i <= node; i++) 

        {

            System.out.print(degree[i] + " ");

        }

    }

  

    // Код драйвера

    public static void main(String[] args) 

    {

        int a[] = {4, 1, 3, 4};

        int n = a.length;

        printDegree(a, n);

    }

}

  
/ * Этот код предоставлен PrinciRaj1992 * /

python3

# Python3 реализация подхода

  
# Функция для печати степеней
# каждый узел в дереве сделан
# заданная последовательность Prufer

def printDegree(prufer, n): 

   

    node = n + 2 

  

    # Хеш-таблица для пометки

    # степень каждого узла

    degree = [1] * (n + 2 + 1

  

    # Увеличить счет степени

    for i in range(0, n): 

        degree[prufer[i]] += 1 

  

    # Печать степени каждого узла

    for i in range(1, node+1):  

        print(degree[i], end = " "

       
# Код драйвера

if __name__ == "__main__":

   

    a = [4, 1, 3, 4

    n = len(a) 

    printDegree(a, n) 

  
# Этот код предоставлен Rituraj Jain

C #

// C # реализация подхода

using System;

      

class GFG 

{

  
// Функция для печати градусов каждого
// узел в дереве сделан
// заданная последовательность Prufer

static void printDegree(int []prufer, int n) 

{

    int node = n + 2;

  

    // Хеш-таблица для пометки

    // степень каждого узла

    int[] degree = new int[n + 2 + 1];

  

    // Первоначально позвольте всем степеням быть 1

    for (int i = 1; i <= node; i++)

    {

        degree[i] = 1;

    }

  

    // Увеличить счет степени

    for (int i = 0; i < n; i++) 

    {

        degree[prufer[i]]++;

    }

  

    // Распечатать степень каждого узла

    for (int i = 1; i <= node; i++) 

    {

        Console.Write(degree[i] + " ");

    }

}

  
// Код драйвера

public static void Main(String[] args) 

{

    int []a = {4, 1, 3, 4};

    int n = a.Length;

    printDegree(a, n);

}
}

  
// Этот код предоставлен 29AjayKumar

Выход:

2 1 2 3 1 1

Рекомендуемые посты:

Вывести степень каждого узла из данной последовательности Prufer

0.00 (0%) 0 votes