Dados los tiempos de inicio y finalización del recorrido DFS de N vértices que están disponibles en un árbol enraizado, la tarea es construir el árbol (imprimir el padre de cada Node).
El padre del Node raíz es 0.
Ejemplos:
Input: Start[] = {2, 4, 1, 0, 3}, End[] = {3, 5, 4, 5, 4}
Output: 3 4 4 0 3
Given Tree is -:
4(0, 5)
/ \
(1, 4)3 2(4, 5)
/ \
(2, 3)1 5(3, 4)
The root will always have start time = 0
processing a node takes 1 unit time but backtracking
does not consume time, so the finishing time
of two nodes can be the same.
Input: Start[] = {4, 3, 2, 1, 0}, End[] = {5, 5, 3, 3, 5}
Output: 2 5 4 5 0
Acercarse:
- La raíz del árbol es el vértice cuyo tiempo de inicio es cero.
- Ahora, es suficiente encontrar los descendientes de un vértice, de esta manera podemos encontrar el padre de cada vértice.
- Defina Identity[i] como el índice del vértice con el inicio igual a i.
- Como Start[v] y End[v] son el tiempo de inicio y finalización del vértice v. El primer hijo de v es Identity[Start[v]+1] y
el (i+1) th es Identity[End[chv[i ]]] donde chv[i] es el i-ésimo hijo del v. - Recorra hacia abajo de manera DFS y actualice el padre de cada Node.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
int N;
// Function to find the parent of each node.
vector<int> Restore_Tree(int Start[], int End[])
{
// Storing index of vertex with starting
// time Equal to i
vector<int> Identity(N,0);
for (int i = 0; i < N; i++)
{
Identity[Start[i]] = i;
}
// Parent array
vector<int> parent(N,-1);
int curr_parent = Identity[0];
for (int j = 1; j < N; j++)
{
// Find the vertex with starting time j
int child = Identity[j];
// If end time of this child is greater than
// (start time + 1), then we traverse down and
// store curr_parent as the parent of child
if (End[child] - j > 1)
{
parent[child] = curr_parent;
curr_parent = child;
}
// Find the parent of current vertex
// over iterating on the finish time
else
parent[child] = curr_parent;
// Backtracking takes zero time
while (End[child]== End[parent[child]])
{
child = parent[child];
curr_parent = parent[child];
if (curr_parent == Identity[0])
break;
}
}
for (int i = 0; i < N; i++)
parent[i] += 1;
// Return the parent array
return parent;
}
// Driver Code
int main()
{
N = 5;
// Start and End time of DFS
int Start[] = {2, 4, 1, 0, 3};
int End[] = {3, 5, 4, 5, 4};
vector<int> a = Restore_Tree(Start, End);
for(int ans:a)
cout << ans << " ";
return 0;
}
// This code is contributed by mohit kumar 29
Java
// Java implementation of above approach
import java.util.Arrays;
class GFG
{
static int N = 5;
// Function to find the parent of each node.
static int[] Restore_Tree(int []S, int []End)
{
// Storing index of vertex with starting
// time Equal to i
int []Identity = new int[N];
for(int i = 0; i < N; i++)
Identity[S[i]] = i;
// Parent array
int []parent = new int[N];
Arrays.fill(parent,-1);
int curr_parent = Identity[0];
for(int j = 1; j < N; j++)
{
// Find the vertex with starting time j
int child = Identity[j];
// If end time of this child is greater than
// (start time + 1), then we traverse down and
// store curr_parent as the parent of child
if(End[child] - j > 1)
{
parent[child] = curr_parent;
curr_parent = child;
}
// Find the parent of current vertex
// over iterating on the finish time
else{
parent[child] = curr_parent;
// Backtracking takes zero time
while(parent[child]>-1 && End[child] == End[parent[child]])
{
child = parent[child];
curr_parent = parent[child];
if(curr_parent == Identity[0])
break;
}
}
}
for(int i = 0; i < N; i++)
parent[i] += 1;
// Return the parent array
return parent;
}
// Driver Code
public static void main(String[] args)
{
// Start and End time of DFS
int []Start = {2, 4, 1, 0, 3};
int []End = {3, 5, 4, 5, 4};
int ans[] =Restore_Tree(Start, End);
for(int a:ans)
System.out.print(a + " ");
}
}
// This code has been contributed by 29AjayKumar
Python
# Python implementation of the above approach # Function to find the parent of each node. def Restore_Tree(S, E): # Storing index of vertex with starting # time Equal to i Identity = N*[0] for i in range(N): Identity[Start[i]] = i # Parent array parent = N*[-1] curr_parent = Identity[0] for j in range(1, N): # Find the vertex with starting time j child = Identity[j] # If end time of this child is greater than # (start time + 1), then we traverse down and # store curr_parent as the parent of child if End[child] - j > 1: parent[child] = curr_parent curr_parent = child # Find the parent of current vertex # over iterating on the finish time else: parent[child] = curr_parent # Backtracking takes zero time while End[child]== End[parent[child]]: child = parent[child] curr_parent = parent[child] if curr_parent == Identity[0]: break for i in range(N): parent[i]+= 1 # Return the parent array return parent # Driver Code if __name__=="__main__": N = 5 # Start and End time of DFS Start = [2, 4, 1, 0, 3] End = [3, 5, 4, 5, 4] print(*Restore_Tree(Start, End))
C#
// C# implementation of the approach
using System;
class GFG
{
static int N = 5;
// Function to find the parent of each node.
static int[] Restore_Tree(int []S, int []End)
{
// Storing index of vertex with starting
// time Equal to i
int []Identity = new int[N];
for(int i = 0; i < N; i++)
Identity[S[i]] = i;
// Parent array
int []parent = new int[N];
for(int i = 0; i < N; i++)
parent[i]=-1;
int curr_parent = Identity[0];
for(int j = 1; j < N; j++)
{
// Find the vertex with starting time j
int child = Identity[j];
// If end time of this child is greater than
// (start time + 1), then we traverse down and
// store curr_parent as the parent of child
if(End[child] - j > 1)
{
parent[child] = curr_parent;
curr_parent = child;
}
// Find the parent of current vertex
// over iterating on the finish time
else
{
parent[child] = curr_parent;
// Backtracking takes zero time
while(parent[child]>-1 && End[child] == End[parent[child]])
{
child = parent[child];
curr_parent = parent[child];
if(curr_parent == Identity[0])
break;
}
}
}
for(int i = 0; i < N; i++)
parent[i] += 1;
// Return the parent array
return parent;
}
// Driver Code
public static void Main(String[] args)
{
// Start and End time of DFS
int []Start = {2, 4, 1, 0, 3};
int []End = {3, 5, 4, 5, 4};
int []ans =Restore_Tree(Start, End);
foreach(int a in ans)
Console.Write(a + " ");
}
}
/* This code contributed by PrinciRaj1992 */
Javascript
<script>
// JavaScript implementation of the approach
var N = 5;
// Function to find the parent of each node.
function Restore_Tree(S, End)
{
// Storing index of vertex with starting
// time Equal to i
var Identity = Array(N);
for(var i = 0; i < N; i++)
Identity[S[i]] = i;
// Parent array
var parent = Array(N);
for(var i = 0; i < N; i++)
parent[i]=-1;
var curr_parent = Identity[0];
for(var j = 1; j < N; j++)
{
// Find the vertex with starting time j
var child = Identity[j];
// If end time of this child is greater than
// (start time + 1), then we traverse down and
// store curr_parent as the parent of child
if(End[child] - j > 1)
{
parent[child] = curr_parent;
curr_parent = child;
}
// Find the parent of current vertex
// over iterating on the finish time
else
{
parent[child] = curr_parent;
// Backtracking takes zero time
while(parent[child]>-1 &&
End[child] == End[parent[child]])
{
child = parent[child];
curr_parent = parent[child];
if(curr_parent == Identity[0])
break;
}
}
}
for(var i = 0; i < N; i++)
parent[i] += 1;
// Return the parent array
return parent;
}
// Driver Code
// Start and End time of DFS
var Start = [2, 4, 1, 0, 3];
var End = [3, 5, 4, 5, 4];
var ans =Restore_Tree(Start, End);
for(var a of ans)
document.write(a + " ");
</script>
Producción:
3 4 4 0 3
Complejidad de tiempo: O(N)
donde N es el número de Nodes en el árbol.
Publicación traducida automáticamente
Artículo escrito por saurabh sisodia y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA