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:
Donde
Total representa el número total de Nodes en Euler Tour Treerepresenta i-ésimo Node en Tree
N dado representa el número total de Nodes en el árbol dadorepresenta el número de hijos de
![$\displaystyle Total=\sum_{node_i=1}^{N} Out_D_e_g[node_i]+1$](https://www.geeksforgeeks.org/wp-content/ql-cache/quicklatex.com-1e1a2c71a2a0fb70e2c48fd39d23e954_l3.png "Rendered by QuickLaTeX.com")
![$\displaystyle Total= N + \sum_{node_i=1}^{N} Out_D_e_g[node_i]$](https://www.geeksforgeeks.org/wp-content/ql-cache/quicklatex.com-b4b59959b2e7d2fa83900948bb93b187_l3.png "Rendered by QuickLaTeX.com")
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