Find the path from root to a vertex such that all K vertices belongs to this path or 1 distance away
Given a tree consisting of N vertices numbered from 1 to N rooted at vertex 1. You are given Q queries. Each query consists of the set of K distinct vertices vi[1], vi[2],…, vi[K]. The task is to determine if there is a path from the root to some vertex X such that each of the given K vertices either belongs to this path or has the distance 1 to some vertex of this path.
Example:
Input: N= 10, Q= 6, edges = {{1, 2}, {1, 3}, {1, 4}, {2, 5}, {2, 6}, {3, 7}, {7, 8}, {7, 9}, {9, 10}}, queries = {{3, 8, 9, 10}, {2, 4, 6}, {2, 1, 5}, {4, 8, 2}, {6, 10}, {5, 4, 7}}
Output:
YES
YES
YES
YES
NO
NOInput: N= 2, Q= 3, edges = {{1, 2}}, queries = {{1, 1}, {1, 2}, {2, 1, 2}}
Output:
YES
YES
YES
Approach: The problem can be solved using the following approach:
The idea is to use Depth-First Search (DFS) to traverse the tree and record entry and exit times for each node. For each query, check if there is a path from the root to some vertex that includes all the parent nodes of the vertices in the query. This is done by comparing the maximum entry time and the minimum exit time among the parent nodes of the vertices in the query. If the minimum exit time is greater than the maximum entry time, it means such a path exists.
Steps-by-step approach:
- Perform DFS: Traverse the tree using Depth-First Search (DFS) starting from the root node. Record the entry and exit times for each node during this traversal.
- Record Parent Nodes: While performing DFS, also keep track of the parent of each node.
- Process Queries: For each query, do the following:
- Find Max Entry and Min Exit Times: Determine the maximum entry time and the minimum exit time among the parent nodes of the vertices in the query.
- Check Path Existence: If the minimum exit time is greater than the maximum entry time, it means there exists a path from the root to some vertex that includes all the parent nodes of the vertices in the query. In this case, output “YES”. Otherwise, output “NO”.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h> using namespace std; const int MAX_NODES = 2E5 + 5; // Declare adjacency list for the graph vector< int > adjacencyList[MAX_NODES]; // Declare arrays for DFS traversal timestamps and parent // nodes int entryTime[MAX_NODES], exitTime[MAX_NODES], parent[MAX_NODES]; // Time counter for DFS traversal int timeCounter = 0; // DFS function to populate entryTime, exitTime, and parent // arrays void depthFirstSearch( int currentNode, int parentNode) { entryTime[currentNode] = timeCounter++; parent[currentNode] = parentNode; for ( auto adjacentNode : adjacencyList[currentNode]) { if (adjacentNode != parentNode) depthFirstSearch(adjacentNode, currentNode); } exitTime[currentNode] = timeCounter++; } int main() { // Provided input int numNodes = 10, numQueries = 6; // Edges of the tree vector<pair< int , int > > edges = { { 1, 2 }, { 1, 3 }, { 1, 4 }, { 2, 5 }, { 2, 6 }, { 3, 7 }, { 7, 8 }, { 7, 9 }, { 9, 10 } }; // Queries vector<vector< int > > queries = { { 3, 8, 9, 10 }, { 2, 4, 6 }, { 2, 1, 5 }, { 4, 8, 2 }, { 6, 10 }, { 5, 4, 7 } }; // Construct the graph for ( auto edge : edges) { int node1 = edge.first, node2 = edge.second; adjacencyList[node1].push_back(node2); adjacencyList[node2].push_back(node1); } // Perform DFS traversal from the root node depthFirstSearch(1, 1); // Process each query for ( auto query : queries) { int numVerticesInQuery = query.size(), maxEntryTime = -1, minExitTime = 1e9; for ( int vertex : query) { vertex = parent[vertex]; // Consider parent of // the vertex for the // path condition minExitTime = min(minExitTime, exitTime[vertex]); maxEntryTime = max(maxEntryTime, entryTime[vertex]); } // If the earliest exit time is later than the // latest entry time, it means there exists a path // satisfying the condition if (minExitTime > maxEntryTime) cout << "YES\n" ; else cout << "NO\n" ; } return 0; } |
Java
import java.util.ArrayList; import java.util.Arrays; import java.util.List; public class TreeQueries { static final int MAX_NODES = 200005 ; // Declare adjacency list for the graph static List<Integer>[] adjacencyList = new ArrayList[MAX_NODES]; // Declare arrays for DFS traversal timestamps and parent nodes static int [] entryTime = new int [MAX_NODES]; static int [] exitTime = new int [MAX_NODES]; static int [] parent = new int [MAX_NODES]; // Time counter for DFS traversal static int timeCounter = 0 ; // DFS function to populate entryTime, exitTime, and parent arrays static void depthFirstSearch( int currentNode, int parentNode) { entryTime[currentNode] = timeCounter++; parent[currentNode] = parentNode; for ( int adjacentNode : adjacencyList[currentNode]) { if (adjacentNode != parentNode) depthFirstSearch(adjacentNode, currentNode); } exitTime[currentNode] = timeCounter++; } public static void main(String[] args) { // Provided input int numNodes = 10 , numQueries = 6 ; // Edges of the tree List< int []> edges = Arrays.asList( new int []{ 1 , 2 }, new int []{ 1 , 3 }, new int []{ 1 , 4 }, new int []{ 2 , 5 }, new int []{ 2 , 6 }, new int []{ 3 , 7 }, new int []{ 7 , 8 }, new int []{ 7 , 9 }, new int []{ 9 , 10 } ); // Queries List<List<Integer>> queries = Arrays.asList( Arrays.asList( 3 , 8 , 9 , 10 ), Arrays.asList( 2 , 4 , 6 ), Arrays.asList( 2 , 1 , 5 ), Arrays.asList( 4 , 8 , 2 ), Arrays.asList( 6 , 10 ), Arrays.asList( 5 , 4 , 7 ) ); // Initialize adjacency list for ( int i = 1 ; i <= numNodes; i++) { adjacencyList[i] = new ArrayList<>(); } // Construct the graph for ( int [] edge : edges) { int node1 = edge[ 0 ], node2 = edge[ 1 ]; adjacencyList[node1].add(node2); adjacencyList[node2].add(node1); } // Perform DFS traversal from the root node depthFirstSearch( 1 , 1 ); // Process each query for (List<Integer> query : queries) { int numVerticesInQuery = query.size(), maxEntryTime = - 1 , minExitTime = ( int ) 1e9; for ( int vertex : query) { vertex = parent[vertex]; // Consider parent of the vertex for the path condition minExitTime = Math.min(minExitTime, exitTime[vertex]); maxEntryTime = Math.max(maxEntryTime, entryTime[vertex]); } // If the earliest exit time is later than the latest entry time, // it means there exists a path satisfying the condition if (minExitTime > maxEntryTime) System.out.println( "YES" ); else System.out.println( "NO" ); } } } // This code is contributed by akshitaguprzj3 |
Python3
MAX_NODES = 2 * 10 * * 5 + 5 # Declare adjacency list for the graph adjacencyList = [[] for _ in range (MAX_NODES)] # Declare arrays for DFS traversal timestamps and parent nodes entryTime = [ 0 ] * MAX_NODES exitTime = [ 0 ] * MAX_NODES parent = [ 0 ] * MAX_NODES # Time counter for DFS traversal timeCounter = 0 # DFS function to populate entryTime, exitTime, and parent arrays def depthFirstSearch(currentNode, parentNode): global timeCounter entryTime[currentNode] = timeCounter timeCounter + = 1 parent[currentNode] = parentNode for adjacentNode in adjacencyList[currentNode]: if adjacentNode ! = parentNode: depthFirstSearch(adjacentNode, currentNode) exitTime[currentNode] = timeCounter timeCounter + = 1 numNodes = 10 numQueries = 6 # Edges of the tree edges = [( 1 , 2 ), ( 1 , 3 ), ( 1 , 4 ), ( 2 , 5 ), ( 2 , 6 ), ( 3 , 7 ), ( 7 , 8 ), ( 7 , 9 ), ( 9 , 10 )] # Queries queries = [ [ 3 , 8 , 9 , 10 ], [ 2 , 4 , 6 ], [ 2 , 1 , 5 ], [ 4 , 8 , 2 ], [ 6 , 10 ], [ 5 , 4 , 7 ] ] # Construct the graph for edge in edges: node1, node2 = edge adjacencyList[node1].append(node2) adjacencyList[node2].append(node1) # Perform DFS traversal from the root node depthFirstSearch( 1 , 1 ) # Process each query for query in queries: numVerticesInQuery = len (query) maxEntryTime = - 1 minExitTime = 10 * * 9 for vertex in query: vertex = parent[vertex] # Consider parent of the vertex for the path condition minExitTime = min (minExitTime, exitTime[vertex]) maxEntryTime = max (maxEntryTime, entryTime[vertex]) # If the earliest exit time is later than the latest entry time, it means there exists a path # satisfying the condition if minExitTime > maxEntryTime: print ( "YES" ) else : print ( "NO" ) |
C#
using System; using System.Collections.Generic; class GFG { const int MAX_NODES = 200005; // Declare adjacency list for the graph static List< int >[] adjacencyList = new List< int >[MAX_NODES]; // Declare arrays for DFS traversal timestamps and parent nodes static int [] entryTime = new int [MAX_NODES]; static int [] exitTime = new int [MAX_NODES]; static int [] parent = new int [MAX_NODES]; // Time counter for DFS traversal static int timeCounter = 0; // DFS function to populate entryTime, exitTime, and parent arrays static void DepthFirstSearch( int currentNode, int parentNode) { entryTime[currentNode] = timeCounter++; parent[currentNode] = parentNode; foreach ( var adjacentNode in adjacencyList[currentNode]) { if (adjacentNode != parentNode) DepthFirstSearch(adjacentNode, currentNode); } exitTime[currentNode] = timeCounter++; } static void Main( string [] args) { // Provided input //int numNodes = 10, numQueries = 6; // Initialize adjacency list for ( int i = 0; i < MAX_NODES; i++) { adjacencyList[i] = new List< int >(); } // Edges of the tree List<Tuple< int , int >> edges = new List<Tuple< int , int >> { Tuple.Create(1, 2), Tuple.Create(1, 3), Tuple.Create(1, 4), Tuple.Create(2, 5), Tuple.Create(2, 6), Tuple.Create(3, 7), Tuple.Create(7, 8), Tuple.Create(7, 9), Tuple.Create(9, 10) }; // Queries List<List< int >> queries = new List<List< int >> { new List< int >{ 3, 8, 9, 10 }, new List< int >{ 2, 4, 6 }, new List< int >{ 2, 1, 5 }, new List< int >{ 4, 8, 2 }, new List< int >{ 6, 10 }, new List< int >{ 5, 4, 7 } }; // Construct the graph foreach ( var edge in edges) { int node1 = edge.Item1, node2 = edge.Item2; adjacencyList[node1].Add(node2); adjacencyList[node2].Add(node1); } // Perform DFS traversal from the root node DepthFirstSearch(1, 1); // Process each query foreach ( var query in queries) { int numVerticesInQuery = query.Count; int maxEntryTime = -1, minExitTime = 1000000000; foreach ( int vertex in query) { int parentVertex = parent[vertex]; // Consider parent of the vertex for // the path condition minExitTime = Math.Min(minExitTime, exitTime[parentVertex]); maxEntryTime = Math.Max(maxEntryTime, entryTime[parentVertex]); } // If the earliest exit time is later than the latest entry time, // it means there exists a path satisfying the condition if (minExitTime > maxEntryTime) Console.WriteLine( "YES" ); else Console.WriteLine( "NO" ); } } } |
Javascript
const MAX_NODES = 200005; // Initialize adjacency list const adjacencyList = new Array(MAX_NODES).fill( null ).map(() => []); // Declare arrays for DFS traversal timestamps and parent nodes const entryTime = new Array(MAX_NODES).fill(0); const exitTime = new Array(MAX_NODES).fill(0); const parent = new Array(MAX_NODES).fill(0); // Time counter for DFS traversal let timeCounter = 0; // DFS function to populate entryTime, exitTime, and parent arrays function depthFirstSearch(currentNode, parentNode) { entryTime[currentNode] = timeCounter++; parent[currentNode] = parentNode; for (const adjacentNode of adjacencyList[currentNode]) { if (adjacentNode !== parentNode) depthFirstSearch(adjacentNode, currentNode); } exitTime[currentNode] = timeCounter++; } // Provided input const edges = [ [1, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [7, 8], [7, 9], [9, 10] ]; const queries = [ [3, 8, 9, 10], [2, 4, 6], [2, 1, 5], [4, 8, 2], [6, 10], [5, 4, 7] ]; // Construct the graph for (const edge of edges) { const [node1, node2] = edge; adjacencyList[node1].push(node2); adjacencyList[node2].push(node1); } // Perform DFS traversal from the root node depthFirstSearch(1, 1); // Process each query for (const query of queries) { let maxEntryTime = -1; let minExitTime = 1000000000; for (const vertex of query) { const parentVertex = parent[vertex]; minExitTime = Math.min(minExitTime, exitTime[parentVertex]); maxEntryTime = Math.max(maxEntryTime, entryTime[parentVertex]); } // If the earliest exit time is later than the latest entry time, // it means there exists a path satisfying the condition if (minExitTime > maxEntryTime) console.log( "YES" ); else console.log( "NO" ); } |
YES YES YES YES NO NO
Time complexity: O(n + q), where n is the number of nodes in the tree and q is the number of queries. This is because the solution performs a DFS traversal on the tree once (which takes O(n) time), and then processes each query in constant time (which takes O(q) time).
Auxiliary space: O(n), where n is the number of nodes in the tree. This is because the solution uses an adjacency list to represent the tree and arrays to store the DFS timestamps and parent nodes for each vertex, all of which require O(n) space