Given a tree with N vertices numbered [0, n – 1], K vertices, and a distance D, the task is to find whether there is a path from the root to some vertex such that each of the K vertices belongs to the path or are at most at a distance D from the path.
Examples:
Input:
0
/ \
/ \
1 2
/ \ / \
/ \ / \
3 4 5 8
/ \
/ \
6 7
/
/
9
K = {6, 7, 8, 5}, D = 1
Output: YES
Explanation:
The path ( 0 - 2 - 5 - 7 )
satisfies the condition. Vertices 5
and 7 are a part of the path.
Vertex 6 is the child of vertex
5 and 8 is the child of 2.
Input:
0
/ \
/ \
1 2
/ \ / \
/ \ / \
3 4 5 8
\ / \
\ / \
10 6 7
/
/
9
K = {10, 9, 8, 5}, D = 2
Output: NO
Explanation:
No such path exists that satisfies the condition.
Approach:
- For every vertex, store their respective parent and depth.
- Select the deepest vertex from the given K vertices
- Keep replacing the K vertices except the root and the deepest vertex by its parent D times
- If the current set of K vertices can form a continuous path, then the answer is Yes or No otherwise.
Below code is the implementation of the above approach:
C++
// C++ implementation of above approach#include <bits/stdc++.h>using namespace std;// Class to represent the Treeclass Tree { int T; // Stores the timing of traversals vector<int> parent; // Stores the parent of each vertex vector<int> depth; // Stores the depth of each vertex vector<int> tin; // Stores the time to reach // every vertex vector<int> tout; // Stores the time of leaving // every vertex after DFS calls // from its children vector<vector<int> > edges; // Store the edgespublic: // Constructor Tree(int n) { T = 0; parent = depth = vector<int>(n); tin = tout = vector<int>(n); edges = vector<vector<int> >(n); } // Adding edges void addEdge(int u, int v) { edges[u].push_back(v); edges[v].push_back(u); } void dfs(int v, int p = -1, int d = 0) { // Store the time to reach vertex v tin[v] = T++; // Store the parent of vertex v parent[v] = p; // Store the depth of vertex v depth[v] = d; // Run DFS for all its children of v for (auto i : edges[v]) { if (i == p) continue; dfs(i, v, d + 1); } // Store the leaving time // of vertex v tout[v] = T++; } // Checks and returns whether vertex // v is parent of vertex u or not bool checkTiming(int v, int u) { if (tin[v] <= tin[u] && tout[u] <= tout[v]) return true; return false; } // Checks and returns if the path exists void pathExistence(vector<int> k, int d) { int deepest_vertex = k[0]; // Find the deepest vertex among the // given K vertices for (int i = 0; i < k.size(); i++) { if (depth[k[i]] > depth[deepest_vertex]) deepest_vertex = k[i]; } // Replace each of the K vertices // except for the root and the // deepest vertex for (int i = 0; i < k.size(); i++) { if (k[i] == deepest_vertex) continue; int count = d; while (count > 0) { // Stop when root // has been reached if (parent[k[i]] == -1) break; k[i] = parent[k[i]]; count--; } } bool ans = true; // Check if each of the K-1 vertices // are a parent of the deepest vertex for (auto i : k) ans &= checkTiming(i, deepest_vertex); if (ans) cout << "Yes" << endl; else cout << "No" << endl; }};// Driver Codeint main(){ Tree t(11); t.addEdge(0, 1); t.addEdge(0, 2); t.addEdge(1, 3); t.addEdge(1, 4); t.addEdge(2, 5); t.addEdge(2, 8); t.addEdge(5, 6); t.addEdge(4, 10); t.addEdge(3, 7); t.addEdge(3, 9); t.dfs(0); vector<int> k = { 2, 6, 8, 5 }; int d = 2; t.pathExistence(k, d); return 0;} |
Java
// Java implementation of above approach import java.util.*;import java.lang.*;class GFG{ static int T; // Stores the timing of traversals static int[] parent; // Stores the parent of each vertex static int[] depth; // Stores the depth of each vertex static int[] tin; // Stores the time to reach // every vertex static int[] tout; // Stores the time of leaving // every vertex after DFS calls // from its children static ArrayList<ArrayList<Integer>> edges; // Adding edges static void addEdge(int u, int v) { edges.get(u).add(v); edges.get(v).add(u); } static void dfs(int v, int p, int d) { // Store the time to reach vertex v tin[v] = T++; // Store the parent of vertex v parent[v] = p; // Store the depth of vertex v depth[v] = d; // Run DFS for all its children of v for(Integer i : edges.get(v)) { if (i == p) continue; dfs(i, v, d + 1); } // Store the leaving time // of vertex v tout[v] = T++; } // Checks and returns whether vertex // v is parent of vertex u or not static boolean checkTiming(int v, int u) { if (tin[v] <= tin[u] && tout[u] <= tout[v]) return true; return false; } // Checks and returns if the path exists static void pathExistence(int[] k, int d) { int deepest_vertex = k[0]; // Find the deepest vertex among the // given K vertices for(int i = 0; i < k.length; i++) { if (depth[k[i]] > depth[deepest_vertex]) deepest_vertex = k[i]; } // Replace each of the K vertices // except for the root and the // deepest vertex for(int i = 0; i < k.length; i++) { if (k[i] == deepest_vertex) continue; int count = d; while (count > 0) { // Stop when root // has been reached if (parent[k[i]] == -1) break; k[i] = parent[k[i]]; count--; } } boolean ans = true; // Check if each of the K-1 vertices // are a parent of the deepest vertex for(int i : k) ans &= checkTiming(i, deepest_vertex); if (ans) System.out.println("Yes"); else System.out.println("No"); } // Driver codepublic static void main(String[] args){ int n = 11; T = 0; parent = new int[n]; depth = new int[n]; tin = new int[n]; tout = new int[n]; edges = new ArrayList<>(); for(int i = 0; i < n; i++) edges.add(new ArrayList<>()); addEdge(0, 1); addEdge(0, 2); addEdge(1, 3); addEdge(1, 4); addEdge(2, 5); addEdge(2, 8); addEdge(5, 6); addEdge(4, 10); addEdge(3, 7); addEdge(3, 9); dfs(0, -1, 0); int[] k = { 2, 6, 8, 5 }; int d = 2; pathExistence(k, d); }}// This code is contributed by offbeat |
Python3
# Python3 implementation of above approachT = 0n = 11 # Stores the timing of traversalsparent = n * [0] # Stores the parent of each vertexdepth = n * [0] # Stores the depth of each vertextin = n * [0] # Stores the time to reach every vertextout = n * [0] # Stores the time of leaving# every vertex after DFS calls# from its childrenedges = []for i in range(n): edges.append([]) # Adding edgesdef addEdge(u, v): edges[u].append(v) edges[v].append(u) def dfs(v, p, d): global T # Store the time to reach vertex v T += 1 tin[v] = T # Store the parent of vertex v parent[v] = p # Store the depth of vertex v depth[v] = d # Run DFS for all its children of v for i in edges[v]: if (i == p): continue dfs(i, v, d + 1) # Store the leaving time # of vertex v T += 1 tout[v] = T # Checks and returns whether vertex# v is parent of vertex u or notdef checkTiming(v, u): if (tin[v] <= tin[u] and tout[u] <= tout[v]): return True return False # Checks and returns if the path existsdef pathExistence(k, d): deepest_vertex = k[0] # Find the deepest vertex among the # given K vertices for i in range(len(k)): if (depth[k[i]] > depth[deepest_vertex]): deepest_vertex = k[i] # Replace each of the K vertices # except for the root and the # deepest vertex for i in range(len(k)): if (k[i] == deepest_vertex): continue count = d while (count > 0): # Stop when root # has been reached if (parent[k[i]] == -1): break k[i] = parent[k[i]] count-=1 ans = True # Check if each of the K-1 vertices # are a parent of the deepest vertex for i in k: ans &= checkTiming(i, deepest_vertex) if ans: print("Yes") else: print("No") addEdge(0, 1)addEdge(0, 2)addEdge(1, 3)addEdge(1, 4)addEdge(2, 5)addEdge(2, 8)addEdge(5, 6)addEdge(4, 10)addEdge(3, 7)addEdge(3, 9) dfs(0, -1, 0) k = [ 2, 6, 8, 5 ]d = 2 pathExistence(k, d)# This code is contributed by divyeshrabadiya07. |
C#
// C# implementation of above approachusing System;using System.Collections.Generic;class GFG { static int T; // Stores the timing of traversals static int[] parent; // Stores the parent of each vertex static int[] depth; // Stores the depth of each vertex static int[] tin; // Stores the time to reach // every vertex static int[] tout; // Stores the time of leaving // every vertex after DFS calls // from its children static List<List<int>> edges; // Adding edges static void addEdge(int u, int v) { edges[u].Add(v); edges[v].Add(u); } static void dfs(int v, int p, int d) { // Store the time to reach vertex v tin[v] = T++; // Store the parent of vertex v parent[v] = p; // Store the depth of vertex v depth[v] = d; // Run DFS for all its children of v foreach(int i in edges[v]) { if (i == p) continue; dfs(i, v, d + 1); } // Store the leaving time // of vertex v tout[v] = T++; } // Checks and returns whether vertex // v is parent of vertex u or not static bool checkTiming(int v, int u) { if (tin[v] <= tin[u] && tout[u] <= tout[v]) return true; return false; } // Checks and returns if the path exists static void pathExistence(int[] k, int d) { int deepest_vertex = k[0]; // Find the deepest vertex among the // given K vertices for(int i = 0; i < k.Length; i++) { if (depth[k[i]] > depth[deepest_vertex]) deepest_vertex = k[i]; } // Replace each of the K vertices // except for the root and the // deepest vertex for(int i = 0; i < k.Length; i++) { if (k[i] == deepest_vertex) continue; int count = d; while (count > 0) { // Stop when root // has been reached if (parent[k[i]] == -1) break; k[i] = parent[k[i]]; count--; } } bool ans = true; // Check if each of the K-1 vertices // are a parent of the deepest vertex foreach(int i in k) ans &= checkTiming(i, deepest_vertex); if (ans) Console.WriteLine("Yes"); else Console.WriteLine("No"); } static void Main() { int n = 11; T = 0; parent = new int[n]; depth = new int[n]; tin = new int[n]; tout = new int[n]; edges = new List<List<int>>(); for(int i = 0; i < n; i++) edges.Add(new List<int>()); addEdge(0, 1); addEdge(0, 2); addEdge(1, 3); addEdge(1, 4); addEdge(2, 5); addEdge(2, 8); addEdge(5, 6); addEdge(4, 10); addEdge(3, 7); addEdge(3, 9); dfs(0, -1, 0); int[] k = { 2, 6, 8, 5 }; int d = 2; pathExistence(k, d); }}// This code is contributed by decode2207. |
Javascript
<script>// Javascript implementation of above approachlet T;// Stores the timing of traversalslet parent;// Stores the parent of each vertexlet depth;// Stores the depth of each vertexlet tin;// Stores the time to reach// every vertexlet tout;// Stores the time of leaving// every vertex after DFS calls// from its childrenlet edges;// Adding edgesfunction addEdge(u, v){ edges[u].push(v); edges[v].push(u);}function dfs(v, p, d){ // Store the time to reach vertex v tin[v] = T++; // Store the parent of vertex v parent[v] = p; // Store the depth of vertex v depth[v] = d; // Run DFS for all its children of v for(let i = 0; i < edges[v].length; i++) { if (edges[v][i] == p) continue; dfs(edges[v][i], v, d + 1); } // Store the leaving time // of vertex v tout[v] = T++;}// Checks and returns whether vertex// v is parent of vertex u or notfunction checkTiming(v, u){ if (tin[v] <= tin[u] && tout[u] <= tout[v]) return true; return false;}// Checks and returns if the path existsfunction pathExistence(k, d){ let deepest_vertex = k[0]; // Find the deepest vertex among the // given K vertices for(let i = 0; i < k.length; i++) { if (depth[k[i]] > depth[deepest_vertex]) deepest_vertex = k[i]; } // Replace each of the K vertices // except for the root and the // deepest vertex for(let i = 0; i < k.length; i++) { if (k[i] == deepest_vertex) continue; let count = d; while (count > 0) { // Stop when root // has been reached if (parent[k[i]] == -1) break; k[i] = parent[k[i]]; count--; } } let ans = true; // Check if each of the K-1 vertices // are a parent of the deepest vertex for(let i = 0; i < k.length; i++) ans &= checkTiming(k[i], deepest_vertex); if (ans) document.write("Yes"); else document.write("No");}// Driver codelet n = 11;T = 0; parent = new Array(n);depth = new Array(n);tin = new Array(n);tout = new Array(n);edges = []; for(let i = 0; i < n; i++) edges.push([]); addEdge(0, 1);addEdge(0, 2);addEdge(1, 3);addEdge(1, 4);addEdge(2, 5);addEdge(2, 8);addEdge(5, 6);addEdge(4, 10);addEdge(3, 7);addEdge(3, 9); dfs(0, -1, 0); let k = [ 2, 6, 8, 5 ];let d = 2; pathExistence(k, d);// This code is contributed by mukesh07</script> |
Output:
Yes
Time Complexity: O(N+K*D) where N is the number of vertices in the tree, K is the number of given vertices, and D is the maximum distance that needs to be traversed from each given vertex.
Space Complexity: O(N), which is used to store the various arrays used in the DFS traversal of the tree.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
