Total de Nodes recorridos en Euler Tour Tree

Ya se ha discutido el recorrido de Euler por el árbol , que aplana la estructura jerárquica del árbol en una array que contiene exactamente 2 * N-1 valores. En este post, la tarea es probar que el grado de Euler Tour Tree es 2 veces el número de Nodes menos uno. Aquí grado significa el número total de Nodes que se atraviesan en Euler Tour.
Ejemplos: 
 

Aporte: 
 

Salida: 15
Entrada: 
 

Salida: 17 
 

Explicación: 
usando el ejemplo 1 :
 

dónde 
 

Se puede ver que el recuento de cada Node en Euler Tour es exactamente igual al grado de salida del Node más 1. 
Matemáticamente, se puede representar como: 
$\displaystyle Total=\sum_{node_i=1}^{N} Out_D_e_g[node_i]+1$
$\displaystyle Total= N + \sum_{node_i=1}^{N} Out_D_e_g[node_i]$
Donde 
Total representa el número total de Nodes en Euler Tour Tree
node_i  representa i-ésimo Node en Tree
N dado representa el número total de Nodes en el árbol dado
Out_D_e_g[node_i]  representa el número de hijos de node_i
 

C++

// C++ program to check the number of nodes
// in Euler Tour tree.
#include <bits/stdc++.h>
using namespace std;
 
#define MAX 1001
 
// Adjacency list representation of tree
vector<int> adj[MAX];
 
// Function to add edges to tree
void add_edge(int u, int v)
{
    adj[u].push_back(v);
}
 
// Program to check if calculated Value is
// equal to 2*size-1
void checkTotalNumberofNodes(int actualAnswer,
                              int size)
{
    int calculatedAnswer = size;
 
    // Add out-degree of each node
    for (int i = 1; i <= size; i++)
        calculatedAnswer += adj[i].size();
 
    if (actualAnswer == calculatedAnswer)
        cout << "Calculated Answer is " << calculatedAnswer
                     << " and is Equal to Actual Answer\n";
    else
        cout << "Calculated Answer is Incorrect\n";
}
int main()
{ // Constructing 1st tree from example
    int N = 8;
    add_edge(1, 2);
    add_edge(1, 3);
    add_edge(2, 4);
    add_edge(2, 5);
    add_edge(3, 6);
    add_edge(3, 7);
    add_edge(6, 8);
 
    // Out_deg[node[i]] is equal to adj[i].size()
    checkTotalNumberofNodes(2 * N - 1, N);
 
    // clear previous stored tree
    for (int i = 1; i <= N; i++)
        adj[i].clear();
 
    // Constructing 2nd tree from example
    N = 9;
    add_edge(1, 2);
    add_edge(1, 3);
    add_edge(2, 4);
    add_edge(2, 5);
    add_edge(2, 6);
    add_edge(3, 9);
    add_edge(5, 7);
    add_edge(5, 8);
 
    // Out_deg[node[i]] is equal to adj[i].size()
    checkTotalNumberofNodes(2 * N - 1, N);
 
    return 0;
}

Java

// Java program to check the number of nodes
// in Euler Tour tree.
import java.util.*;
 
class GFG
{
    static final int MAX = 1001;
 
    // Adjacency list representation of tree
    static Vector<Integer>[] adj = new Vector[MAX];
 
    // Function to add edges to tree
    static void add_edge(int u, int v)
    {
        adj[u].add(v);
    }
 
    // Program to check if calculated Value is
    // equal to 2*size-1
    static void checkTotalNumberofNodes(int actualAnswer,
                                        int size)
    {
        int calculatedAnswer = size;
 
        // Add out-degree of each node
        for (int i = 1; i <= size; i++)
            calculatedAnswer += adj[i].size();
 
        if (actualAnswer == calculatedAnswer)
            System.out.print("Calculated Answer is " +
                                    calculatedAnswer +
                  " and is Equal to Actual Answer\n");
        else
            System.out.print("Calculated Answer is Incorrect\n");
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        for (int i = 0; i < MAX; i++)
            adj[i] = new Vector<Integer>();
             
        // Constructing 1st tree from example
        int N = 8;
        add_edge(1, 2);
        add_edge(1, 3);
        add_edge(2, 4);
        add_edge(2, 5);
        add_edge(3, 6);
        add_edge(3, 7);
        add_edge(6, 8);
 
        // Out_deg[node[i]] is equal to adj[i].size()
        checkTotalNumberofNodes(2 * N - 1, N);
 
        // clear previous stored tree
        for (int i = 1; i <= N; i++)
            adj[i].clear();
 
        // Constructing 2nd tree from example
        N = 9;
        add_edge(1, 2);
        add_edge(1, 3);
        add_edge(2, 4);
        add_edge(2, 5);
        add_edge(2, 6);
        add_edge(3, 9);
        add_edge(5, 7);
        add_edge(5, 8);
 
        // Out_deg[node[i]] is equal to adj[i].size()
        checkTotalNumberofNodes(2 * N - 1, N);
    }
}
 
// This code is contributed by Rajput-Ji

C#

// C# program to check the number
// of nodes in Euler Tour tree.
using System;
using System.Collections.Generic;
 
class GFG
{
    static readonly int MAX = 1001;
 
    // Adjacency list representation of tree
    static List<int>[] adj = new List<int>[MAX];
 
    // Function to add edges to tree
    static void add_edge(int u, int v)
    {
        adj[u].Add(v);
    }
 
    // Program to check if calculated Value is
    // equal to 2*size-1
    static void checkTotalNumberofNodes(int actualAnswer,
                                        int size)
    {
        int calculatedAnswer = size;
 
        // Add out-degree of each node
        for (int i = 1; i <= size; i++)
            calculatedAnswer += adj[i].Count;
 
        if (actualAnswer == calculatedAnswer)
            Console.Write("Calculated Answer is " +
                                 calculatedAnswer +
               " and is Equal to Actual Answer\n");
        else
            Console.Write("Calculated Answer " +
                              "is Incorrect\n");
    }
 
    // Driver Code
    public static void Main(String[] args)
    {
        for (int i = 0; i < MAX; i++)
            adj[i] = new List<int>();
             
        // Constructing 1st tree from example
        int N = 8;
        add_edge(1, 2);
        add_edge(1, 3);
        add_edge(2, 4);
        add_edge(2, 5);
        add_edge(3, 6);
        add_edge(3, 7);
        add_edge(6, 8);
 
        // Out_deg[node[i]] is equal to adj[i].Count
        checkTotalNumberofNodes(2 * N - 1, N);
 
        // clear previous stored tree
        for (int i = 1; i <= N; i++)
            adj[i].Clear();
 
        // Constructing 2nd tree from example
        N = 9;
        add_edge(1, 2);
        add_edge(1, 3);
        add_edge(2, 4);
        add_edge(2, 5);
        add_edge(2, 6);
        add_edge(3, 9);
        add_edge(5, 7);
        add_edge(5, 8);
 
        // Out_deg[node[i]] is equal to adj[i].Count
        checkTotalNumberofNodes(2 * N - 1, N);
    }
}
 
// This code is contributed by PrinciRaj1992

Javascript

<script>
 
// Javascript program to check the number
// of nodes in Euler Tour tree.
var MAX = 1001;
 
// Adjacency list representation of tree
var adj = Array.from(Array(MAX), ()=>Array());
 
// Function to add edges to tree
function add_edge(u, v)
{
    adj[u].push(v);
}
 
// Program to check if calculated Value is
// equal to 2*size-1
function checkTotalNumberofNodes(actualAnswer, size)
{
    var calculatedAnswer = size;
     
    // push out-degree of each node
    for (var i = 1; i <= size; i++)
        calculatedAnswer += adj[i].length;
    if (actualAnswer == calculatedAnswer)
        document.write("Calculated Answer is " +
                             calculatedAnswer +
           " and is Equal to Actual Answer<br>");
    else
        document.write("Calculated Answer " +
                          "is Incorrect<br>");
}
 
// Driver Code
for (var i = 0; i < MAX; i++)
    adj[i] = [];
     
// Constructing 1st tree from example
var N = 8;
add_edge(1, 2);
add_edge(1, 3);
add_edge(2, 4);
add_edge(2, 5);
add_edge(3, 6);
add_edge(3, 7);
add_edge(6, 8);
 
// Out_deg[node[i]] is equal to adj[i].Count
checkTotalNumberofNodes(2 * N - 1, N);
 
// clear previous stored tree
for (var i = 1; i <= N; i++)
    adj[i] = []
     
// Constructing 2nd tree from example
N = 9;
add_edge(1, 2);
add_edge(1, 3);
add_edge(2, 4);
add_edge(2, 5);
add_edge(2, 6);
add_edge(3, 9);
add_edge(5, 7);
add_edge(5, 8);
 
// Out_deg[node[i]] is equal to adj[i].Count
checkTotalNumberofNodes(2 * N - 1, N);
 
// This code is contributed by itsok.
</script>

Producción: 
 

Calculated Answer is 15 and is Equal to Actual Answer
Calculated Answer is 17 and is Equal to Actual Answer

Publicación traducida automáticamente

Artículo escrito por Abhishek rajput y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *