Dado un árbol con N vértices numerados de 0 a N – 1 y una consulta Q que contiene Nodes en el árbol, la tarea es encontrar el Node principal del Node dado para múltiples consultas. Considere el Node 0 como el Node raíz y tome el padre del Node raíz como la raíz misma.
Ejemplos:
Tree: 0 / \ 1 2 | / \ 3 4 5 Input: N = 2 Output: 0 Explanation: Parent of node 2 is node 0 i.e root node Input: N = 3 Output: 1 Explanation: Parent of node 3 is node 1
Enfoque :
De forma predeterminada, asignamos el padre del Node raíz como la propia raíz. Luego, recorremos el árbol usando Breadth First Traversal (BFS). Cuando marcamos los elementos secundarios de los Nodes como visitados, también asignamos el Node principal de estos elementos secundarios como el Node s. Finalmente, para diferentes consultas, se imprime el valor del padre[] del Node.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation for // the above approach #include <bits/stdc++.h> using namespace std; const int sz = 1e5; // Adjacency list representation // of the tree vector<int> tree[sz + 1]; // Boolean array to mark all the // vertices which are visited bool vis[sz + 1]; // Array of vector where ith index // stores the path from the root // node to the ith node int ans[sz + 1]; // Function to create an // edge between two vertices void addEdge(int a, int b) { // Add a to b's list tree[a].push_back(b); // Add b to a's list tree[b].push_back(a); } // Modified Breadth-First Function void bfs(int node) { // Create a queue of {child, parent} queue<pair<int, int> > qu; // Push root node in the front of qu.push({ node, 0 }); while (!qu.empty()) { pair<int, int> p = qu.front(); // Dequeue a vertex from queue qu.pop(); ans[p.first] = p.second; vis[p.first] = true; // Get all adjacent vertices of the dequeued // vertex s. If any adjacent has not // been visited then enqueue it for (int child : tree[p.first]) { if (!vis[child]) { qu.push({ child, p.first }); } } } } // Driver code int main() { // Number of vertices int n = 6; addEdge(0, 1); addEdge(0, 2); addEdge(1, 3); addEdge(2, 4); addEdge(2, 5); // Calling modified bfs function bfs(0); int q[] = { 2, 3 }; for (int i = 0; i < 2; i++) { cout << ans[q[i]] << '\n'; } return 0; }
Java
// Java implementation for // the above approach import java.util.*; class GFG { static int sz = (int) 1e5; // Adjacency list representation // of the tree static Vector<Integer> []tree = new Vector[sz + 1]; // Boolean array to mark all the // vertices which are visited static boolean []vis = new boolean[sz + 1]; // Array of vector where ith index // stores the path from the root // node to the ith node static int []ans = new int[sz + 1]; static class pair { int first, second; public pair(int first, int second) { this.first = first; this.second = second; } } // Function to create an // edge between two vertices static void addEdge(int a, int b) { // Add a to b's list tree[a].add(b); // Add b to a's list tree[b].add(a); } // Modified Breadth-First Function static void bfs(int node) { // Create a queue of {child, parent} Queue<pair> qu = new LinkedList<>(); // Push root node in the front of qu.add(new pair(node, 0 )); while (!qu.isEmpty()) { pair p = qu.peek(); // Dequeue a vertex from queue qu.remove(); ans[p.first] = p.second; vis[p.first] = true; // Get all adjacent vertices of the dequeued // vertex s. If any adjacent has not // been visited then enqueue it for (int child : tree[p.first]) { if (!vis[child]) { qu.add(new pair(child, p.first )); } } } } // Driver code public static void main(String[] args) { // Number of vertices int n = 6; for (int i = 0; i < sz + 1; i++) tree[i] = new Vector<Integer>(); addEdge(0, 1); addEdge(0, 2); addEdge(1, 3); addEdge(2, 4); addEdge(2, 5); // Calling modified bfs function bfs(0); int q[] = { 2, 3 }; for (int i = 0; i < 2; i++) { System.out.println(ans[q[i]]); } } } // This code is contributed by 29AjayKumar
Python3
# Python implementation for # the above approach sz = 10**5 # Adjacency list representation # of the tree tree = [[] for _ in range(sz + 1)] # Boolean array to mark all the # vertices which are visited vis = [0] * (sz + 1) # Array of vector where ith index # stores the path from the root # node to the ith node ans = [0] * (sz + 1) # Function to create an # edge between two vertices def addEdge(a, b): # Add a to b's list tree[a].append(b) # Add b to a's list tree[b].append(a) # Modified Breadth-First Function def bfs(node): # Create a queue of child, parent qu = [] # Push root node in the front of qu.append([node, 0]) while (len(qu)): p = qu[0] # Dequeue a vertex from queue qu.pop(0) ans[p[0]] = p[1] vis[p[0]] = True # Get all adjacent vertices of the dequeued # vertex s. If any adjacent has not # been visited then enqueue it for child in tree[p[0]]: if (not vis[child]): qu.append([child, p[0]]) # Driver code # Number of vertices n = 6 addEdge(0, 1) addEdge(0, 2) addEdge(1, 3) addEdge(2, 4) addEdge(2, 5) # Calling modified bfs function bfs(0) q = [2, 3] for i in range(2): print(ans[q[i]]) # This code is contributed by SHUBHAMSINGH10
C#
// C# implementation of the approach using System; using System.Collections.Generic; class GFG { static int sz = (int) 1e5; // Adjacency list representation // of the tree static List<int> []tree = new List<int>[sz + 1]; // Boolean array to mark all the // vertices which are visited static Boolean []vis = new Boolean[sz + 1]; // Array of vector where ith index // stores the path from the root // node to the ith node static int []ans = new int[sz + 1]; public class pair { public int first, second; public pair(int first, int second) { this.first = first; this.second = second; } } // Function to create an // edge between two vertices static void addEdge(int a, int b) { // Add a to b's list tree[a].Add(b); // Add b to a's list tree[b].Add(a); } // Modified Breadth-First Function static void bfs(int node) { // Create a queue of {child, parent} Queue<pair> qu = new Queue<pair>(); // Push root node in the front of qu.Enqueue(new pair(node, 0 )); while (qu.Count != 0) { pair p = qu.Peek(); // Dequeue a vertex from queue qu.Dequeue(); ans[p.first] = p.second; vis[p.first] = true; // Get all adjacent vertices of the dequeued // vertex s. If any adjacent has not // been visited then enqueue it foreach (int child in tree[p.first]) { if (!vis[child]) { qu.Enqueue(new pair(child, p.first )); } } } } // Driver code public static void Main(String[] args) { // Number of vertices for (int i = 0; i < sz + 1; i++) tree[i] = new List<int>(); addEdge(0, 1); addEdge(0, 2); addEdge(1, 3); addEdge(2, 4); addEdge(2, 5); // Calling modified bfs function bfs(0); int []q = { 2, 3 }; for (int i = 0; i < 2; i++) { Console.WriteLine(ans[q[i]]); } } } // This code is contributed by 29AjayKumar
Javascript
<script> // JavaScript implementation for the above approach let sz = 1e5; // Adjacency list representation // of the tree let tree = new Array(sz + 1); // Boolean array to mark all the // vertices which are visited let vis = new Array(sz + 1); vis.fill(false); // Array of vector where ith index // stores the path from the root // node to the ith node let ans = new Array(sz + 1); ans.fill(0); // Function to create an // edge between two vertices function addEdge(a, b) { // Add a to b's list tree[a].push(b); // Add b to a's list tree[b].push(a); } // Modified Breadth-First Function function bfs(node) { // Create a queue of {child, parent} let qu = []; // Push root node in the front of qu.push([node, 0 ]); while (qu.length > 0) { let p = qu[0]; // Dequeue a vertex from queue qu.shift(); ans[p[0]] = p[1]; vis[p[0]] = true; // Get all adjacent vertices of the dequeued // vertex s. If any adjacent has not // been visited then enqueue it for (let child = 0; child < tree[p[0]].length; child++) { if (!vis[tree[p[0]][child]]) { qu.push([tree[p[0]][child], p[0]]); } } } } // Number of vertices let n = 6; for (let i = 0; i < sz + 1; i++) tree[i] = []; addEdge(0, 1); addEdge(0, 2); addEdge(1, 3); addEdge(2, 4); addEdge(2, 5); // Calling modified bfs function bfs(0); let q = [ 2, 3 ]; for (let i = 0; i < 2; i++) { document.write(ans[q[i]] + "</br>"); } </script>
0 1
Complejidad temporal: O(N)
Espacio auxiliar: O(N)