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>
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