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

Опубликовано: 5 Января, 2022

Дано дерево с N вершинами, пронумерованными от 0 до N - 1, где 0 - корневой узел. Задача состоит в том, чтобы проверить, является ли узел листовым, для нескольких запросов.
Примеры:

 Вход:
       0
     / 
   1 2
 / 
3 4 
    /
  5
q [] = {0, 3, 4, 5}
Выход:
Нет
да
Нет
да
На графике 2, 3 и 5 - единственные листовые узлы.

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Подход: сохраните степень всех вершин в массиве degree [] . Для каждого ребра от A до B степень [A] и степень [B] увеличиваются на 1 . Теперь каждый узел, который не является корневым узлом и имеет степень 1, является листовым узлом, а все остальные узлы - нет.
Ниже представлена реализация описанного выше подхода:

C ++

 // C++ implementation of the approach
 #include <bits/stdc++.h>
 using namespace std;
 // Function to calculate the degree of all the vertices
 void init( int degree[], vector<pair< int , int > > edges, int n)
 {
    // Initializing degree of all the vertices as 0
    for ( int i = 0; i < n; i++) {
        degree[i] = 0;
    }
    // For each edge from A to B, degree[A] and degree[B]
    // are increased by 1
    for ( int i = 0; i < edges.size(); i++) {
        degree[edges[i].first]++;
        degree[edges[i].second]++;
    }
 }
 // Function to perform the queries
 void performQueries(vector<pair< int , int > > edges,
                    vector< int > q, int n)
 {
    // To store the of degree
    // of all the vertices
    int degree[n]; 
    // Calculate the degree for all the vertices
    init(degree, edges, n);
    // For every query
    for ( int i = 0; i < q.size(); i++) { 
        int node = q[i];
        if (node == 0) {
            cout << "No
" ;
            continue ;
        }
        // If the current node has 1 degree
        if (degree[node] == 1)
            cout << "Yes
" ;
        else
            cout << "No
" ;
    }
 }
 // Driver code
 int main()
 {
    // Number of vertices
    int n = 6; 
    // Edges of the tree
    vector<pair< int , int > > edges = {
        { 0, 1 }, { 0, 2 }, { 1, 3 }, { 1, 4 }, { 4, 5 }
    };
    // Queries
    vector< int > q = { 0, 3, 4, 5 }; 
    // Perform the queries
    performQueries(edges, q, n);
    return 0;
 }

Джава

 // Java implementation of the approach
 import java.util.*;
 class GFG
 {
 static pair class
 {
    int first, second;
    public pair( int first, int second)
    {
        this .first = first;
        this .second = second;
    }
 }
 // Function to calculate the degree
 // of all the vertices
 static void init( int degree[],
                     pair[] edges, int n)
 {
    // Initializing degree of
    // all the vertices as 0
    for ( int i = 0 ; i < n; i++)
    {
        degree[i] = 0 ;
    }
    // For each edge from A to B,
    // degree[A] and degree[B]
    // are increased by 1
    for ( int i = 0 ; i < edges.length; i++)
    {
        degree[edges[i].first]++;
        degree[edges[i].second]++;
    }
 }
 // Function to perform the queries
 static void performQueries(pair [] edges,
                           int []q, int n)
 {
    // To store the of degree
    // of all the vertices
    int []degree = new int [n]; 
    // Calculate the degree for all the vertices
    init(degree, edges, n);
    // For every query
    for ( int i = 0 ; i < q.length; i++)
    {
        int node = q[i];
        if (node == 0 )
        {
            System.out.println( "No" );
            continue ;
        }
        
        // If the current node has 1 degree
        if (degree[node] == 1 )
            System.out.println( "Yes" );
        else
            System.out.println( "No" );
    }
 }
 // Driver code
 public static void main(String[] args)
 {
    // Number of vertices
    int n = 6 ; 
    // Edges of the tree
    pair[] edges = { new pair( 0 , 1 ),
                    new pair( 0 , 2 ),
                    new pair( 1 , 3 ),
                    new pair( 1 , 4 ),
                    new pair( 4 , 5 )}; 
    // Queries
    int []q = { 0 , 3 , 4 , 5 }; 
    // Perform the queries
    performQueries(edges, q, n);
 }
 }
 // This code is contributed by Rajput-Ji

Python3

 # Python3 implementation of the approach
 # Function to calculate the degree
 # of all the vertices
 def init(degree, edges, n) : 
    # Initializing degree of
    # all the vertices as 0
    for i in range (n) :
        degree[i] = 0 ; 
    # For each edge from A to B,
    # degree[A] and degree[B]
    # are increased by 1
    for i in range ( len (edges)) :
        degree[edges[i][ 0 ]] + = 1 ;
        degree[edges[i][ 1 ]] + = 1 ;
 # Function to perform the queries
 def performQueries(edges, q, n) : 
    # To store the of degree
    # of all the vertices
    degree = [ 0 ] * n; 
    # Calculate the degree for all the vertices
    init(degree, edges, n);
    # For every query
    for i in range ( len (q)) : 
        node = q[i];
        if (node = = 0 ) :
            print ( "No" );
            continue ; 
        # If the current node has 1 degree
        if (degree[node] = = 1 ) :
            print ( "Yes" );
        else :
            print ( "No" );
 # Driver code
 if __name__ = = "__main__" : 
    # Number of vertices
    n = 6 ; 
    # Edges of the tree
    edges = [[ 0 , 1 ], [ 0 , 2 ],
             [ 1 , 3 ], [ 1 , 4 ],
             [ 4 , 5 ]]; 
    # Queries
    q = [ 0 , 3 , 4 , 5 ]; 
    # Perform the queries
    performQueries(edges, q, n);
 # This code is contributed by AnkitRai01

C #

 // C# implementation of the approach
 using System;
                    
class GFG
 {
 pair public class
 {
    public int first, second;
    public pair( int first, int second)
    {
        this .first = first;
        this .second = second;
    }
 }
 // Function to calculate the degree
 // of all the vertices
 static void init( int []degree,
                 pair[] edges, int n)
 {
    // Initializing degree of
    // all the vertices as 0
    for ( int i = 0; i < n; i++)
    {
        degree[i] = 0;
    }
    // For each edge from A to B,
    // degree[A] and degree[B]
    // are increased by 1
    for ( int i = 0; i < edges.Length; i++)
    {
        degree[edges[i].first]++;
        degree[edges[i].second]++;
    }
 }
 // Function to perform the queries
 static void performQueries(pair [] edges,
                            int []q, int n)
 {
    // To store the of degree
    // of all the vertices
    int []degree = new int [n]; 
    // Calculate the degree for all the vertices
    init(degree, edges, n);
    // For every query
    for ( int i = 0; i < q.Length; i++)
    {
        int node = q[i];
        if (node == 0)
        {
            Console.WriteLine( "No" );
            continue ;
        }
        
        // If the current node has 1 degree
        if (degree[node] == 1)
            Console.WriteLine( "Yes" );
        else
            Console.WriteLine( "No" );
    }
 }
 // Driver code
 public static void Main(String[] args)
 {
    // Number of vertices
    int n = 6; 
    // Edges of the tree
    pair[] edges = { new pair(0, 1),
                    new pair(0, 2),
                    new pair(1, 3),
                    new pair(1, 4),
                    new pair(4, 5)}; 
    // Queries
    int []q = { 0, 3, 4, 5 }; 
    // Perform the queries
    performQueries(edges, q, n);
 }
 }
 // This code is contributed by 29AjayKumar

Javascript

 <script>
 // JavaScript implementation of the approach
 // Function to calculate the degree of all the vertices
 function init(degree, edges, n)
 {
    // Initializing degree of all the vertices as 0
    for ( var i = 0; i < n; i++) {
        degree[i] = 0;
    }
    // For each edge from A to B, degree[A] and degree[B]
    // are increased by 1
    for ( var i = 0; i < edges.length; i++) {
        degree[edges[i][0]]++;
        degree[edges[i][1]]++;
    }
 }
 // Function to perform the queries
 function performQueries( edges, q, n)
 {
    // To store the of degree
    // of all the vertices
    var degree = Array(n); 
    // Calculate the degree for all the vertices
    init(degree, edges, n);
    // For every query
    for ( var i = 0; i < q.length; i++) { 
        var node = q[i];
        if (node == 0) {
            document.write( "No<br>" );
            continue ;
        }
        // If the current node has 1 degree
        if (degree[node] == 1)
            document.write( "Yes<br>" );
        else
            document.write( "No<br>" );
    }
 }
 // Driver code
 // Number of vertices
 var n = 6;
 // Edges of the tree
 var edges = [
    [ 0, 1 ], [ 0, 2 ], [ 1, 3 ], [ 1, 4 ], [ 4, 5 ]
 ];
 // Queries
 var q = [ 0, 3, 4, 5 ];
 // Perform the queries
 performQueries(edges, q, n);
 </script>

Выход:

 Нет
да
Нет
да

Сложность времени: O (n)

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Получите все важные математические концепции для соревновательного программирования с курсом Essential Maths for CP по доступной для студентов цене.

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.

Technical Scripter Олимпиады по программированию Структуры данных

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

C ++

Джава

Python3

C #

Javascript

РЕКОМЕНДУЕМЫЕ СТАТЬИ