Рубрики

Выведите узел с максимальной степенью в последовательности prufer

При заданной последовательности дерева Пруфера задача состоит в том, чтобы напечатать узел с максимальной степенью в дереве, чья последовательность Пруфера задана. Если существует множество узлов с максимальной степенью, выведите узел с наименьшим номером.

Примеры:

Input: a[] = {4, 1, 3, 4} 
Output: 4
The tree is:
2----4----3----1----5
     |
     6 

Input: a[] = {1, 2, 2} 
Output: 2

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

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

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

C ++

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

using namespace std;

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

int findMaxDegreeNode(int prufer[], int n)

{

    int nodes = n + 2;

  

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

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

    int degree[n + 2 + 1];

  

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

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

        degree[i] = 1;

  

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

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

        degree[prufer[i]]++;

  

    int maxDegree = 0;

    int node = 0;

  

    // Найти узел с максимальной степенью

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

        if (degree[i] > maxDegree) {

            maxDegree = degree[i];

            node = i;

        }

    }

  

    return node;

}

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

int main()

{

    int a[] = { 1, 2, 2 };

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

    cout << findMaxDegreeNode(a, n);

  

    return 0;

}

Джава

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

import java.io.*;

  

class GFG 

{

          

    // Функция для возврата узла с

    // максимальная степень в дереве

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

    static int findMaxDegreeNode(int prufer[], int n) 

    

        int nodes = n + 2

      

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

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

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

      

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

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

            degree[i] = 1

      

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

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

            degree[prufer[i]]++; 

      

        int maxDegree = 0

        int node = 0

      

        // Найти узел с максимальной степенью

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

        

            if (degree[i] > maxDegree) 

            

                maxDegree = degree[i]; 

                node = i; 

            

        

      

        return node; 

    

      

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

    public static void main (String[] args) 

    {

  

        int []a = { 1, 2, 2 }; 

        int n = a.length;

        System.out.println(findMaxDegreeNode(a, n)); 

    

}

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

python3

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

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

def findMaxDegreeNode(prufer, n):

    nodes = n + 2;

   

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

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

    degree = [0]*(n + 2 + 1);

   

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

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

        degree[i] = 1;

   

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

    for i in range(n):

        degree[prufer[i]]+=1;

   

    maxDegree = 0;

    node = 0;

   

    # Найти узел с максимальной степенью

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

        if (degree[i] > maxDegree):

            maxDegree = degree[i];

            node = i;

  

    return node;

  

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

a = [ 1, 2, 2 ];

n = len(a);

print(findMaxDegreeNode(a, n));

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

C #

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

using System;

  

class GFG

{

      

    // Функция для возврата узла с

    // максимальная степень в дереве

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

    static int findMaxDegreeNode(int []prufer, int n) 

    

        int nodes = n + 2; 

      

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

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

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

      

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

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

            degree[i] = 1; 

      

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

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

            degree[prufer[i]]++; 

      

        int maxDegree = 0; 

        int node = 0; 

      

        // Найти узел с максимальной степенью

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

        

            if (degree[i] > maxDegree) 

            

                maxDegree = degree[i]; 

                node = i; 

            

        

      

        return node; 

    

      

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

    static public void Main () 

    

        int []a = { 1, 2, 2 }; 

        int n = a.Length; 

          

        Console.WriteLine(findMaxDegreeNode(a, n)); 

    

}

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

Выход:

2

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

Выведите узел с максимальной степенью в последовательности prufer

0.00 (0%) 0 votes