Find node U containing all nodes from a set V at atmost distance 1 from the path from root to U | C ++ program for the above approach ; To store the time ; Function to perform DFS to store times , distance and parent of each node ; Update the distance of node u ; Update parent of node u ; Increment time timeT ; Discovery time of node u ; Traverse the adjacency list of current node and recursively call DFS for each vertex ; If current node Adj [ u ] [ i ] is unvisited ; Update the finishing time ; Function to add edges between nodes u and v ; Function to find the node U such that path from root to U contains nodes in V [ ] ; Initialise vis , dis , parent , preTime , and postTime ; Store Adjacency List ; Create adjacency List ; Perform DFS Traversal ; Stores the distance of deepest vertex ' u ' ; Update the deepest node by traversing the qu [ ] ; Find deepest vertex ; Replace each vertex with it 's  corresponding parent except  the root vertex ; Checks if the ancestor with respect to deepest vertex u ; Update ans ; Print the result ; Driver Code ; Total vertices ; Given set of vertices ; Given edges ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; int timeT = 0 ; 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 [ ] ) { distance [ u ] = dis ; parent [ u ] = p ; vis [ u ] = 1 ; timeT ++ ; preTime [ u ] = timeT ; for ( int i = 0 ; i < Adj [ u ] . size ( ) ; i ++ ) { if ( vis [ Adj [ u ] [ i ] ] == 0 ) { dfs ( Adj [ u ] [ i ] , u , dis + 1 , vis , distance , parent , preTime , postTime , Adj ) ; } } timeT ++ ; postTime [ u ] = timeT ; } void addEdge ( vector < int > Adj [ ] , int u , int v ) { Adj [ u ] . push_back ( v ) ; Adj [ v ] . push_back ( u ) ; } void findNodeU ( int N , int V , int Vertices [ ] , int Edges [ ] [ 2 ] ) { 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 ) ; vector < int > Adj [ N + 1 ] ; int u , v ; for ( int i = 0 ; i < N - 1 ; i ++ ) { addEdge ( Adj , Edges [ i ] [ 0 ] , Edges [ i ] [ 1 ] ) ; } dfs ( 1 , 0 , 0 , vis , distance , parent , preTime , postTime , Adj ) ; int maximumDistance = 0 ; maximumDistance = 0 ; for ( int k = 0 ; k < V ; k ++ ) { if ( maximumDistance < distance [ Vertices [ k ] ] ) { maximumDistance = distance [ Vertices [ k ] ] ; u = Vertices [ k ] ; } if ( parent [ Vertices [ k ] ] != 0 ) { Vertices [ k ] = parent [ Vertices [ k ] ] ; } } bool ans = true ; bool flag ; for ( int k = 0 ; k < V ; k ++ ) { if ( preTime [ Vertices [ k ] ] <= preTime [ u ] && postTime [ Vertices [ k ] ] >= postTime [ u ] ) flag = true ; else flag = false ; ans = ans & flag ; } if ( ans ) cout << u ; else cout << " NO " ; } int main ( ) { int N = 10 ; int V = 5 ; int Vertices [ ] = { 4 , 3 , 8 , 9 , 10 } ; int Edges [ ] [ 2 ] = { { 1 , 2 } , { 1 , 3 } , { 1 , 4 } , { 2 , 5 } , { 2 , 6 } , { 3 , 7 } , { 7 , 8 } , { 7 , 9 } , { 9 , 10 } } ; findNodeU ( N , V , Vertices , Edges ) ; return 0 ; }