Find node U containing all nodes from a set V at atmost distance 1 from the path from root to U
Given a N-ary tree with N vertices rooted at 1 and a set of vertices as V[], the task is to print any such vertex U such that the path from the root to U consists of all the vertices from V[] at utmost distance 1. If no vertex is obtained, then print “No”. Else, print the value of U.
Examples:
Input: N = 10, Edges[][] = {{1, 2}, {1, 3}, {1, 4}, {2, 5}, {2, 6}, {3, 7}, {7, 8}, {7, 9}, {9, 10}}, V[] = {4, 3, 8, 9, 10}
Output: 10
Explanation: Path from root to node 10 contain {1, 3, 7, 9, 10} and 8 is at distance 1 from this path.Input: N = 10, Edges[][] = {{1, 2}, {1, 3}, {1, 4}, {2, 5}, {2, 6}, {3, 7}, {7, 8}, {7, 9}, {9, 10}}, V[] = {3, 4, 2, 8}
Output: 8
Explanation: Path from root to node 8 contain {1, 3, 7, 8}. Now, 4 and 2 are at distance 1 from this path.
Naive Approach: The naive idea is to find all possible path from the root 1 to every node and choose the one which contains all the required vertices of the given set V[] in the path from the root to that chosen vertex or has a distance 1 from that path.
Time Complexity: O(N!)
Auxiliary Space: O(N2)
Efficient Approach: The above approach can be optimized by precomputing the distances of every vertex from root. This pre-computing helps in finding if some vertex P is a parent of some other vertex C in the given tree or not. Below are the steps:
- Perform DFS Traversal from the root node 1 and store the pre and post visited time of each node in the given tree.
- Now, vertex V is the parent of the vertex U if and only if the pre-time of V is smaller than or equal to the pre-time of U and post time of U is greater than or equal to post time of V.
- It can be noted that the path of the deepest vertex in the given set V[] from the root vertex is the required result.
- Now, the problem reduced to check if every vertex’s parent in the given set V[] is the ancestor of the deepest vertex in set V[].
- Therefore, replace each vertex with its parent(except the root) and check that each parent is the ancestor of the deepest vertex by above mention property.
- If the condition satisfies then print the deepest vertex, otherwise print “No”.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // To store the time int timeT = 0; // Function to perform DFS // to store times, distance // and parent of each node void dfs( int u, int p, int dis, vector< int >& vis, vector< int >& distance, vector< int >& parent, vector< int >& preTime, vector< int >& postTime, vector< int > Adj[]) { // Update the distance of node u distance[u] = dis; // Update parent of node u parent[u] = p; vis[u] = 1; // Increment time timeT timeT++; // Discovery time of node u preTime[u] = timeT; // Traverse the adjacency list // of current node and recursively // call DFS for each vertex for ( int i = 0; i < Adj[u].size(); i++) { // If current node Adj[u][i] // is unvisited if (vis[Adj[u][i]] == 0) { dfs(Adj[u][i], u, dis + 1, vis, distance, parent, preTime, postTime, Adj); } } timeT++; // Update the finishing time postTime[u] = timeT; } // Function to add edges between // nodes u and v void addEdge(vector< int > Adj[], int u, int v) { Adj[u].push_back(v); Adj[v].push_back(u); } // Function to find the node U // such that path from root to U // contains nodes in V[] void findNodeU( int N, int V, int Vertices[], int Edges[][2]) { // Initialise vis, dis, parent, // preTime, and postTime vector< int > vis(N + 1, 0); vector< int > distance(N + 1, 0); vector< int > parent(N + 1, 0); vector< int > preTime(N + 1, 0); vector< int > postTime(N + 1, 0); // Store Adjacency List vector< int > Adj[N + 1]; int u, v; // Create adjacency List for ( int i = 0; i < N - 1; i++) { addEdge(Adj, Edges[i][0], Edges[i][1]); } // Perform DFS Traversal dfs(1, 0, 0, vis, distance, parent, preTime, postTime, Adj); int maximumDistance = 0; // Stores the distance // of deepest vertex 'u' maximumDistance = 0; // Update the deepest node by // traversing the qu[] for ( int k = 0; k < V; k++) { // Find deepest vertex if (maximumDistance < distance[Vertices[k]]) { maximumDistance = distance[Vertices[k]]; u = Vertices[k]; } // Replace each vertex with it's // corresponding parent except // the root vertex if (parent[Vertices[k]] != 0) { Vertices[k] = parent[Vertices[k]]; } } bool ans = true ; bool flag; for ( int k = 0; k < V; k++) { // Checks if the ancestor // with respect to deepest // vertex u if (preTime[Vertices[k]] <= preTime[u] && postTime[Vertices[k]] >= postTime[u]) flag = true ; else flag = false ; // Update ans ans = ans & flag; } // Print the result if (ans) cout << u; else cout << "NO" ; } // Driver Code int main() { // Total vertices int N = 10; int V = 5; // Given set of vertices int Vertices[] = { 4, 3, 8, 9, 10 }; // Given edges int Edges[][2] = { { 1, 2 }, { 1, 3 }, { 1, 4 }, { 2, 5 }, { 2, 6 }, { 3, 7 }, { 7, 8 }, { 7, 9 }, { 9, 10 } }; // Function Call findNodeU(N, V, Vertices, Edges); return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG{ // To store the time static int timeT = 0 ; // Function to perform DFS // to store times, distance // and parent of each node static void dfs( int u, int p, int dis, int vis[], int distance[], int parent[], int preTime[], int postTime[], ArrayList<ArrayList<Integer>> Adj) { // Update the distance of node u distance[u] = dis; // Update parent of node u parent[u] = p; vis[u] = 1 ; // Increment time timeT timeT++; // Discovery time of node u preTime[u] = timeT; // Traverse the adjacency list // of current node and recursively // call DFS for each vertex for ( int i = 0 ; i < Adj.get(u).size(); i++) { // If current node Adj[u][i] // is unvisited if (vis[Adj.get(u).get(i)] == 0 ) { dfs(Adj.get(u).get(i), u, dis + 1 , vis, distance, parent, preTime, postTime, Adj); } } timeT++; // Update the finishing time postTime[u] = timeT; } // Function to add edges between // nodes u and v static void addEdge(ArrayList<ArrayList<Integer>> Adj, int u, int v) { Adj.get(u).add(v); Adj.get(v).add(u); } // Function to find the node U // such that path from root to U // contains nodes in V[] static void findNodeU( int N, int V, int Vertices[], int Edges[][]) { // Initialise vis, dis, parent, // preTime, and postTime int vis[] = new int [N + 1 ]; int distance[] = new int [N + 1 ]; int parent[] = new int [N + 1 ]; int preTime[] = new int [N + 1 ]; int postTime[] = new int [N + 1 ]; // Store Adjacency List ArrayList< ArrayList<Integer>> Adj = new ArrayList<>(); for ( int i = 0 ; i < N + 1 ; i++) Adj.add( new ArrayList<Integer>()); int u = 0 , v; // Create adjacency List for ( int i = 0 ; i < N - 1 ; i++) { addEdge(Adj, Edges[i][ 0 ], Edges[i][ 1 ]); } // Perform DFS Traversal dfs( 1 , 0 , 0 , vis, distance, parent, preTime, postTime, Adj); int maximumDistance = 0 ; // Stores the distance // of deepest vertex 'u' maximumDistance = 0 ; // Update the deepest node by // traversing the qu[] for ( int k = 0 ; k < V; k++) { // Find deepest vertex if (maximumDistance < distance[Vertices[k]]) { maximumDistance = distance[Vertices[k]]; u = Vertices[k]; } // Replace each vertex with it's // corresponding parent except // the root vertex if (parent[Vertices[k]] != 0 ) { Vertices[k] = parent[Vertices[k]]; } } boolean ans = true ; boolean flag; for ( int k = 0 ; k < V; k++) { // Checks if the ancestor // with respect to deepest // vertex u if (preTime[Vertices[k]] <= preTime[u] && postTime[Vertices[k]] >= postTime[u]) flag = true ; else flag = false ; // Update ans ans = ans & flag; } // Print the result if (ans) System.out.println(u); else System.out.println( "NO" ); } // Driver Code public static void main(String[] args) { // Total vertices int N = 10 ; int V = 5 ; // Given set of vertices int Vertices[] = { 4 , 3 , 8 , 9 , 10 }; // Given edges int Edges[][] = { { 1 , 2 }, { 1 , 3 }, { 1 , 4 }, { 2 , 5 }, { 2 , 6 }, { 3 , 7 }, { 7 , 8 }, { 7 , 9 }, { 9 , 10 } }; // Function call findNodeU(N, V, Vertices, Edges); } } // This code is contributed by jrishabh99 |
Python3
# Python3 program for the above approach # To store the time timeT = 0 ; # Function to perform DFS # to store times, distance # and parent of each node def dfs(u, p, dis, vis, distance, parent, preTime, postTime, Adj): global timeT # Update the distance of node u distance[u] = dis; # Update parent of node u parent[u] = p; vis[u] = 1 ; # Increment time timeT timeT + = 1 # Discovery time of node u preTime[u] = timeT; # Traverse the adjacency list # of current node and recursively # call DFS for each vertex for i in range ( len (Adj[u])): # If current node Adj[u][i] # is unvisited if (vis[Adj[u][i]] = = 0 ): dfs(Adj[u][i], u, dis + 1 , vis, distance, parent, preTime, postTime, Adj); timeT + = 1 # Update the finishing time postTime[u] = timeT; # Function to add edges between # nodes u and v def addEdge(Adj,u, v): Adj[u].append(v); Adj[v].append(u); # Function to find the node U # such that path from root to U # contains nodes in V[] def findNodeU(N, V, Vertices, Edges): # Initialise vis, dis, parent, # preTime, and postTime vis = [ 0 for i in range (N + 1 )] distance = [ 0 for i in range (N + 1 )] parent = [ 0 for i in range (N + 1 )] preTime = [ 0 for i in range (N + 1 )] postTime = [ 0 for i in range (N + 1 )] # Store Adjacency List Adj = [[] for i in range (N + 1 )] u = 0 v = 0 # Create adjacency List for i in range (N - 1 ): addEdge(Adj, Edges[i][ 0 ], Edges[i][ 1 ]); # Perform DFS Traversal dfs( 1 , 0 , 0 , vis, distance, parent, preTime, postTime, Adj); maximumDistance = 0 ; # Stores the distance # of deepest vertex 'u' maximumDistance = 0 ; # Update the deepest node by # traversing the qu[] for k in range (V): # Find deepest vertex if (maximumDistance < distance[Vertices[k]]): maximumDistance = distance[Vertices[k]]; u = Vertices[k]; # Replace each vertex with it's # corresponding parent except # the root vertex if (parent[Vertices[k]] ! = 0 ): Vertices[k] = parent[Vertices[k]]; ans = True ; flag = False for k in range (V): # Checks if the ancestor # with respect to deepest # vertex u if (preTime[Vertices[k]] < = preTime[u] and postTime[Vertices[k]] > = postTime[u]): flag = True ; else : flag = False ; # Update ans ans = ans & flag; # Print the result if (ans): print (u) else : print ( 'No' ) # Driver Code if __name__ = = '__main__' : # Total vertices N = 10 ; V = 5 ; # Given set of vertices Vertices = [ 4 , 3 , 8 , 9 , 10 ]; # Given edges Edges = [ [ 1 , 2 ], [ 1 , 3 ], [ 1 , 4 ], [ 2 , 5 ], [ 2 , 6 ], [ 3 , 7 ], [ 7 , 8 ], [ 7 , 9 ], [ 9 , 10 ] ]; # Function Call findNodeU(N, V, Vertices, Edges); # This code is contributed by rutvik_56 |
C#
// C# program for // the above approach using System; using System.Collections.Generic; class GFG{ // To store the time static int timeT = 0; // Function to perform DFS // to store times, distance // and parent of each node static void dfs( int u, int p, int dis, int []vis, int []distance, int []parent, int []preTime, int []postTime, List<List< int >> Adj) { // Update the distance of node u distance[u] = dis; // Update parent of node u parent[u] = p; vis[u] = 1; // Increment time timeT timeT++; // Discovery time of node u preTime[u] = timeT; // Traverse the adjacency list // of current node and recursively // call DFS for each vertex for ( int i = 0; i < Adj[u].Count; i++) { // If current node Adj[u,i] // is unvisited if (vis[Adj[u][i]] == 0) { dfs(Adj[u][i], u, dis + 1, vis, distance, parent, preTime, postTime, Adj); } } timeT++; // Update the finishing time postTime[u] = timeT; } // Function to add edges between // nodes u and v static void addEdge(List<List< int >> Adj, int u, int v) { Adj[u].Add(v); Adj[v].Add(u); } // Function to find the node U // such that path from root to U // contains nodes in V[] static void findNodeU( int N, int V, int []Vertices, int [,]Edges) { // Initialise vis, dis, parent, // preTime, and postTime int []vis = new int [N + 1]; int []distance = new int [N + 1]; int []parent = new int [N + 1]; int []preTime = new int [N + 1]; int []postTime = new int [N + 1]; // Store Adjacency List List<List< int >> Adj = new List<List< int >>(); for ( int i = 0; i < N + 1; i++) Adj.Add( new List< int >()); int u = 0, v; // Create adjacency List for ( int i = 0; i < N - 1; i++) { addEdge(Adj, Edges[i, 0], Edges[i, 1]); } // Perform DFS Traversal dfs(1, 0, 0, vis, distance, parent, preTime, postTime, Adj); int maximumDistance = 0; // Stores the distance // of deepest vertex 'u' maximumDistance = 0; // Update the deepest node by // traversing the qu[] for ( int k = 0; k < V; k++) { // Find deepest vertex if (maximumDistance < distance[Vertices[k]]) { maximumDistance = distance[Vertices[k]]; u = Vertices[k]; } // Replace each vertex with it's // corresponding parent except // the root vertex if (parent[Vertices[k]] != 0) { Vertices[k] = parent[Vertices[k]]; } } bool ans = true ; bool flag; for ( int k = 0; k < V; k++) { // Checks if the ancestor // with respect to deepest // vertex u if (preTime[Vertices[k]] <= preTime[u] && postTime[Vertices[k]] >= postTime[u]) flag = true ; else flag = false ; // Update ans ans = ans & flag; } // Print the result if (ans) Console.WriteLine(u); else Console.WriteLine( "NO" ); } // Driver Code public static void Main(String[] args) { // Total vertices int N = 10; int V = 5; // Given set of vertices int []Vertices = {4, 3, 8, 9, 10}; // Given edges int [,]Edges = {{1, 2}, {1, 3}, {1, 4}, {2, 5}, {2, 6}, {3, 7}, {7, 8}, {7, 9}, {9, 10}}; // Function call findNodeU(N, V, Vertices, Edges); } } // This code is contributed by gauravrajput1 |
Javascript
<script> // JavaScript implementation of the above approach // To store the time let timeT = 0; // Function to perform DFS // to store times, distance // and parent of each node function dfs(u, p, dis, vis, distance, parent, preTime, postTime, Adj) { // Update the distance of node u distance[u] = dis; // Update parent of node u parent[u] = p; vis[u] = 1; // Increment time timeT timeT++; // Discovery time of node u preTime[u] = timeT; // Traverse the adjacency list // of current node and recursively // call DFS for each vertex for (let i = 0; i < Adj[u].length; i++) { // If current node Adj[u,i] // is unvisited if (vis[Adj[u][i]] == 0) { dfs(Adj[u][i], u, dis + 1, vis, distance, parent, preTime, postTime, Adj); } } timeT++; // Update the finishing time postTime[u] = timeT; } // Function to add edges between // nodes u and v function addEdge(Adj, u, v) { Adj[u].push(v); Adj[v].push(u); } // Function to find the node U // such that path from root to U // contains nodes in V[] function findNodeU(N, V, Vertices, Edges) { // Initialise vis, dis, parent, // preTime, and postTime let vis = new Array(N + 1); vis.fill(0); let distance = new Array(N + 1); distance.fill(0); let parent = new Array(N + 1); parent.fill(0); let preTime = new Array(N + 1); preTime.fill(0); let postTime = new Array(N + 1); postTime.fill(0); // Store Adjacency List let Adj = []; for (let i = 0; i < N + 1; i++) Adj.push([]); let u = 0, v; // Create adjacency List for (let i = 0; i < N - 1; i++) { addEdge(Adj, Edges[i][0], Edges[i][1]); } // Perform DFS Traversal dfs(1, 0, 0, vis, distance, parent, preTime, postTime, Adj); let maximumDistance = 0; // Stores the distance // of deepest vertex 'u' maximumDistance = 0; // Update the deepest node by // traversing the qu[] for (let k = 0; k < V; k++) { // Find deepest vertex if (maximumDistance < distance[Vertices[k]]) { maximumDistance = distance[Vertices[k]]; u = Vertices[k]; } // Replace each vertex with it's // corresponding parent except // the root vertex if (parent[Vertices[k]] != 0) { Vertices[k] = parent[Vertices[k]]; } } let ans = true ; let flag; for (let k = 0; k < V; k++) { // Checks if the ancestor // with respect to deepest // vertex u if (preTime[Vertices[k]] <= preTime[u] && postTime[Vertices[k]] >= postTime[u]) flag = true ; else flag = false ; // Update ans ans = ans & flag; } // Print the result if (ans) document.write(u); else document.write( "NO" ); } // Total vertices let N = 10; let V = 5; // Given set of vertices let Vertices = [4, 3, 8, 9, 10]; // Given edges let Edges = [[1, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [7, 8], [7, 9], [9, 10]]; // Function call findNodeU(N, V, Vertices, Edges); </script> |
10
Time Complexity: O(N + V), where N is the total vertices and V is the size of the given set.
Auxiliary Space: O(5*N)