Encuentre el Node Kth en el recorrido DFS de un subárbol dado en un árbol

Dado un árbol con N Nodes y dos enteros K y V . La tarea es encontrar el Node Kth en el recorrido DFS del vértice V .
Considere el siguiente árbol:

DFS del Node número 1 es [1, 2, 3, 5, 6, 8, 7, 9, 4]. 
El DFS del número de Node 3 es [3, 5, 6, 8, 7, 9] 
El DFS del número de Node 7 es [7, 9] El 
DFS del número de Node 9 es [9].

Imprime “-1” si los números en el DFS del vértice V son menores que K.

Ejemplos: 

Input : Tree: Shown in above image, V = 3, K = 4
Output : 8

Input : Tree: Shown in above image, V = 7, K = 3
Output : -1

Enfoque : construyamos un vector p : para almacenar el recorrido DFS del árbol completo desde el vértice 1. Sea tin v la posición del vértice V en el vector p (el tamaño del vector p en el momento en que llamamos DFS desde el vértice V) y tout v sea la posición del primer vértice empujado al vector después de dejar el subárbol del vértice V (el tamaño del vector p en el momento en que regresamos de DFS desde el vértice V). Entonces es obvio que el subárbol del vértice V está en el intervalo [tin v , tout v ).
Entonces, para encontrar el Node K-ésimo en el DFS del subárbol del Node V, tendremos que devolver el Node K-ésimo en el intervalo [tin v , tout v ].

A continuación se muestra la implementación del enfoque anterior:

C++

// C++ program to find the Kth node in the
// DFS traversal of the subtree of given
// vertex V in a Tree
 
#include <bits/stdc++.h>
using namespace std;
#define N 100005
 
// To store nodes
int n;
vector<int> tree[N];
 
// To store the current index of vertex in DFS
int currentIdx;
 
// To store the starting index and ending
// index of vertex in the DFS traversal array
vector<int> startIdx, endIdx;
 
// To store the DFS of vertex 1
vector<int> p;
 
// Function to add edge between two nodes
void Add_edge(int u, int v)
{
    tree[u].push_back(v);
    tree[v].push_back(u);
}
 
// Initialize the vectors
void intisalise()
{
    startIdx.resize(n);
    endIdx.resize(n);
    p.resize(n);
}
 
// Function to perform DFS of a vertex
// 1. stores the DFS of the vertex 1 in vector p,
// 2. store the start index of DFS of every vertex
// 3. store the end index of DFS of every vertex
void Dfs(int ch, int par)
{
    p[currentIdx] = ch;
 
    // store starting index of node ch
    startIdx[ch] = currentIdx++;
 
    for (auto c : tree[ch]) {
        if (c != par)
            Dfs(c, ch);
    }
 
    // store ending index
    endIdx[ch] = currentIdx - 1;
}
 
// Function to find the Kth node in DFS of vertex V
int findNode(int v, int k)
{
    k += startIdx[v] - 1;
 
    // check if kth number exits or not
    if (k <= endIdx[v])
        return p[k];
 
    return -1;
}
 
// Driver code
int main()
{
    // number of nodes
    n = 9;
 
    // add edges
    Add_edge(1, 2);
    Add_edge(1, 3);
    Add_edge(1, 4);
    Add_edge(3, 5);
    Add_edge(3, 7);
    Add_edge(5, 6);
    Add_edge(5, 8);
    Add_edge(7, 9);
 
    intisalise();
 
    // store DFS of 1st node
    Dfs(1, 0);
 
    int v = 3, k = 4;
 
    cout << findNode(v, k);
 
    return 0;
}

Java

// Java program to find the Kth node in the
// DFS traversal of the subtree of given
// vertex V in a Tree
import java.util.*;
 
class GFG{
     
static int N = 100005;
 
// To store nodes
static int n;
 
static ArrayList<
       ArrayList<Integer>> tree = new ArrayList<>();
 
// To store the current index of vertex in DFS
static int currentIdx;
 
// To store the starting index and ending
// index of vertex in the DFS traversal array
static int[] startIdx;
static int[] endIdx;
 
// To store the DFS of vertex 1
static int[] p;
 
// Function to add edge between two nodes
static void Add_edge(int u, int v)
{
    tree.get(u).add(v);
    tree.get(v).add(u);
}
 
// Initialize the vectors
static void intisalise()
{
    startIdx = new int[n + 1];
    endIdx = new int[n + 1];
    p = new int[n + 1];
}
 
// Function to perform DFS of a vertex
// 1. stores the DFS of the vertex 1 in vector p,
// 2. store the start index of DFS of every vertex
// 3. store the end index of DFS of every vertex
static void Dfs(int ch, int par)
{
    p[currentIdx] = ch;
 
    // store starting index of node ch
    startIdx[ch] = currentIdx++;
 
    for(int c : tree.get(ch))
    {
        if (c != par)
            Dfs(c, ch);
    }
 
    // store ending index
    endIdx[ch] = currentIdx - 1;
}
 
// Function to find the Kth node
// in DFS of vertex V
static int findNode(int v, int k)
{
    k += startIdx[v] - 1;
 
    // Check if kth number exits or not
    if (k <= endIdx[v])
        return p[k];
 
    return -1;
}
 
// Driver code
public static void main(String[] args)
{
     
    // Number of nodes
    n = 9;
 
    for(int i = 0; i <= n; i++)
        tree.add(new ArrayList<Integer>());
         
    // Add edges
    Add_edge(1, 2);
    Add_edge(1, 3);
    Add_edge(1, 4);
    Add_edge(3, 5);
    Add_edge(3, 7);
    Add_edge(5, 6);
    Add_edge(5, 8);
    Add_edge(7, 9);
 
    intisalise();
 
    // Store DFS of 1st node
    Dfs(1, 0);
 
    int v = 3, k = 4;
 
    System.out.println(findNode(v, k));
}
}
 
// This code is contributed by jrishabh99

Python3

# Python3 program to find the Kth node in the
# DFS traversal of the subtree of given
# vertex V in a Tree
N = 100005
 
n = 10
tree = [[]for i in range(N)]
 
# To store the current index of vertex in DFS
currentIdx = 0
 
# To store the starting index and ending
# index of vertex in the DFS traversal array
startIdx = [0 for i in range(n)]
endIdx = [0 for i in range(n)]
 
# To store the DFS of vertex 1
p = [0 for i in range(n)]
 
# Function to add edge between two nodes
def Add_edge(u, v):
    tree[u].append(v)
    tree[v].append(u)
 
# Initialize the vectors
def intisalise():
    pass
 
# Function to perform DFS of a vertex
# 1. stores the DFS of the vertex 1 in vector p,
# 2. store the start index of DFS of every vertex
# 3. store the end index of DFS of every vertex
def Dfs(ch, par):
    global currentIdx
 
    p[currentIdx] = ch
 
    # store starting index of node ch
    startIdx[ch] = currentIdx
    currentIdx += 1
 
    for c in tree[ch]:
        if (c != par):
            Dfs(c, ch)
 
    # store ending index
    endIdx[ch] = currentIdx - 1
 
# Function to find the Kth node in
# DFS of vertex V
def findNode(v, k):
 
    k += startIdx[v] - 1
 
    # check if kth number exits or not
    if (k <= endIdx[v]):
        return p[k]
 
    return -1
 
# Driver code
 
# number of nodes
n = 9
 
# add edges
Add_edge(1, 2)
Add_edge(1, 3)
Add_edge(1, 4)
Add_edge(3, 5)
Add_edge(3, 7)
Add_edge(5, 6)
Add_edge(5, 8)
Add_edge(7, 9)
 
intisalise()
 
# store DFS of 1st node
Dfs(1, 0)
 
v, k = 3, 4
 
print(findNode(v, k))
 
# This code is contributed by mohit kumar

C#

// C# program to find the Kth node in the
// DFS traversal of the subtree of given
// vertex V in a Tree
using System;
using System.Collections;
using System.Collections.Generic;
   
class GFG{
   
// To store nodes
static int n;
   
static ArrayList tree = new ArrayList();
   
// To store the current index of vertex in DFS
static int currentIdx;
   
// To store the starting index and ending
// index of vertex in the DFS traversal array
static int[] startIdx;
static int[] endIdx;
   
// To store the DFS of vertex 1
static int[] p;
   
// Function to add edge between two nodes
static void Add_edge(int u, int v)
{
    ((ArrayList)tree[u]).Add(v);
    ((ArrayList)tree[v]).Add(u);
}
   
// Initialize the vectors
static void intisalise()
{
    startIdx = new int[n + 1];
    endIdx = new int[n + 1];
    p = new int[n + 1];
}
   
// Function to perform DFS of a vertex
// 1. stores the DFS of the vertex 1 in vector p,
// 2. store the start index of DFS of every vertex
// 3. store the end index of DFS of every vertex
static void Dfs(int ch, int par)
{
    p[currentIdx] = ch;
   
    // store starting index of node ch
    startIdx[ch] = currentIdx++;
   
    foreach(int c in (ArrayList)tree[ch])
    {
        if (c != par)
            Dfs(c, ch);
    }
   
    // store ending index
    endIdx[ch] = currentIdx - 1;
}
   
// Function to find the Kth node 
// in DFS of vertex V
static int findNode(int v, int k)
{
    k += startIdx[v] - 1;
   
    // Check if kth number exits or not
    if (k <= endIdx[v])
        return p[k];
   
    return -1;
}
   
// Driver code
public static void Main(string[] args)
{
     
    // Number of nodes
    n = 9;
   
    for(int i = 0; i <= n; i++)
        tree.Add(new ArrayList());
           
    // Add edges
    Add_edge(1, 2);
    Add_edge(1, 3);
    Add_edge(1, 4);
    Add_edge(3, 5);
    Add_edge(3, 7);
    Add_edge(5, 6);
    Add_edge(5, 8);
    Add_edge(7, 9);
   
    intisalise();
   
    // Store DFS of 1st node
    Dfs(1, 0);
   
    int v = 3, k = 4;
   
    Console.Write(findNode(v, k));
}
}
 
// This code is contributed by rutvik_56

Javascript

<script>
// Javascript program to find the Kth node in the
// DFS traversal of the subtree of given
// vertex V in a Tree
 
let N = 100005;
 
// To store nodes
let n=10;
 
let tree = [];
// To store the current index of vertex in DFS
let currentIdx=0;
 
// To store the starting index and ending
// index of vertex in the DFS traversal array
let startIdx;
let endIdx;
 
// To store the DFS of vertex 1
let p;
 
// Function to add edge between two nodes
function Add_edge(u,v)
{
    tree[u].push(v);
    tree[v].push(u);
}
 
// Initialize the vectors
function intisalise()
{
    startIdx = new Array(n + 1);
    endIdx = new Array(n + 1);
    p = new Array(n + 1);
    for(let i=0;i<(n+1);i++)
    {
        startIdx[i]=0;
        endIdx[i]=0;
        p[i]=0;
    }
}
 
// Function to perform DFS of a vertex
// 1. stores the DFS of the vertex 1 in vector p,
// 2. store the start index of DFS of every vertex
// 3. store the end index of DFS of every vertex
function Dfs(ch,par)
{
    p[currentIdx] = ch;
  
    // store starting index of node ch
    startIdx[ch] = currentIdx++;
  
    for(let c=0;c<tree[ch].length;c++)
    {
        if (tree[ch] != par)
            Dfs(tree[ch], ch);
    }
  
    // store ending index
    endIdx[ch] = currentIdx - 1;
}
 
// Function to find the Kth node
// in DFS of vertex V
function findNode(v,k)
{
    k += startIdx[v] - 1;
  
    // Check if kth number exits or not
    if (k <= endIdx[v])
        return p[k];
  
    return -1;
}
 
// Driver code
// Number of nodes
    n = 9;
  
    for(let i = 0; i <= n; i++)
        tree.push([]);
          
    // Add edges
    Add_edge(1, 2);
    Add_edge(1, 3);
    Add_edge(1, 4);
    Add_edge(3, 5);
    Add_edge(3, 7);
    Add_edge(5, 6);
    Add_edge(5, 8);
    Add_edge(7, 9);
  
    intisalise();
    // Store DFS of 1st node
    Dfs(1, 0);
  
    let v = 3, k = 4;
  
    document.write(findNode(v, k));
 
 
// This code is contributed by unknown2108
</script>
Producción: 

8

 

Publicación traducida automáticamente

Artículo escrito por pawan_asipu 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 *