Given a tree (a connected, undirected graph with no cycles) consisting of n nodes numbered from 1 to n. You are also given a 2d integer array edges[] where edges[i] = [x, y] means there exists an undirected edge between x and y. An announcement is being made from one of the nodes of the given tree but Geek doesn’t know from which one. Instead, he knows the nodes from which the announcement can be heard. Given such m nodes from where the announcement can be heard which is represented by an integer array canBeHeardFrom[] of length m and an integer loudness representing the loudness of the announcement, your task is to find the number of possible nodes from where the announcement might be going on.
Note: If the loudness of the announcement is x then it can be heard from all the nodes that are up to x distance away from the announcement nodes.
Examples:
Input : n = 7, m = 2, canBeHeardFrom[] = {3, 5}, loudness = 3, edges[][] = { {1, 2}, {1, 3}, {2, 4}, {2, 5}, {3, 6}, {3, 7}}
Output: 5
Explanation: The announcement node must be from either of the nodes {1, 2, 3, 4, 5}Input: n = 3, m = 1, canBeHeardFrom[] = {1}, loudness = 3, edges[][] = { {1, 2}, {1, 3}}
Output : 3
Approach :
Here we are trying to find nodes up to a loudness distance away from m nodes.
- Firstly we are putting m nodes into the HashSet.
- Then form an adjacency array for all edges.
- Initialize the dp1[] and dp2[] array with -1.
- dfs1(node, par, adj, hs):
- In this function, there are parameters node, parent node, adjacency array, and HashSet.
- This function will find out all the distances from where the announcement can be made from root node 1.
- In this function, 1 is the root node, and dp1[] stores the maximum node from where the announcement can be heard.
- Here if 1 is the announcement node then we are doing dp2[1] = 0.
- dfs2(node, par, adj, hs):
- Here in this function, we are following the re-routing concept.
- Here the intuition behind this function is for every node you need to calculate the maximum point till which the announcement can be heard.
- For example, If we are at node 3 then the maximum point from where the announcement can be heard is 3(The announcement is heard from node 5).
- Here if we are considering Input:1, we can see how dp2 is look like
- After calculating dp1 and dp2, we have to count all nodes that have maximum loudness(≤ loudness) from the m nodes.
- Then return the count of those nodes.
Below is the implementation of this approach:
C++
// C++ code for the above approach #include <bits/stdc++.h> using namespace std; class Solution { public : // Initialising of dp vectors vector< int > dp1, dp2; int findAnnouncementNodes( int n, int m, vector< int >& canBeHeardFrom, int d, vector<vector< int > >& edges) { vector< int > adj[n + 5]; set< int > hs; for ( int x : canBeHeardFrom) hs.insert(x); for ( auto e : edges) { adj[e[0]].push_back(e[1]); adj[e[1]].push_back(e[0]); } // Resizing vectors dp1.resize(n + 5, -1); dp2.resize(n + 5, -1); // Traversing through dfs dfs1(1, 0, adj, hs); if (hs.find(1) != hs.end()) dp2[1] = 0; // Traversing through dfs dfs2(1, 0, adj, hs); int count = 0; for ( int i = 1; i <= n; i++) if (dp1[i] <= d && dp2[i] <= d) count++; return count; } // Function to traverse through edges void dfs2( int node, int par, vector< int >* adj, set< int >& hs) { int max1 = -1, max2 = -1; for ( int ngr : adj[node]) { if (ngr != par) { if (dp1[ngr] > max1) { max2 = max1; max1 = dp1[ngr]; } else if (dp1[ngr] > max2) { max2 = dp1[ngr]; } } } for ( int ngr : adj[node]) { if (ngr != par) { int dist = (dp1[ngr] == max1 ? max2 : max1); if (dist != -1) dp2[ngr] = dist + 2; if (dp2[node] != -1) { dp2[ngr] = max(dp2[ngr], 1 + dp2[node]); } if (hs.find(ngr) != hs.end()) dp2[ngr] = max(dp2[ngr], 0); dfs2(ngr, node, adj, hs); } } } // Function to traverse through edges int dfs1( int node, int par, vector< int >* adj, set< int >& hs) { if (hs.find(node) != hs.end()) dp1[node] = 0; for ( int ngr : adj[node]) { if (ngr != par) { int dis = dfs1(ngr, node, adj, hs); if (dis != -1) dp1[node] = max(dp1[node], 1 + dis); } } return dp1[node]; } }; // Driver code int main() { int n = 7, m = 2, loudness = 3; vector< int > canBeHeardFrom; canBeHeardFrom.assign({ 3, 5 }); vector<vector< int > > edges{ { { 1, 2 }, { 1, 3 }, { 2, 4 }, { 2, 5 }, { 3, 6 }, { 3, 7 } } }; Solution obj; // Function call int res = obj.findAnnouncementNodes( n, m, canBeHeardFrom, loudness, edges); cout << res << endl; } |
Java
// Java code for the above approach import java.io.*; import java.util.*; class Solution { // Initializing dp integer arrays int [] dp1, dp2; Solution() { // Giving size to the arrays dp1 = new int [ 100005 ]; dp2 = new int [ 100005 ]; Arrays.fill(dp1, - 1 ); Arrays.fill(dp2, - 1 ); } public int findAnnouncementNodes( int n, int m, List<Integer> canBeHeardFrom, int d, List<List<Integer> > edges) { List<List<Integer> > adj = new ArrayList<>(); for ( int i = 0 ; i <= n + 5 ; i++) { adj.add( new ArrayList<Integer>()); } HashSet<Integer> hs = new HashSet<Integer>(canBeHeardFrom); for (List<Integer> e : edges) { int u = e.get( 0 ); int v = e.get( 1 ); adj.get(u).add(v); adj.get(v).add(u); } // Traversing through dfs dfs1( 1 , 0 , adj, hs); if (hs.contains( 1 )) { dp2[ 1 ] = 0 ; } // Traversing through dfs dfs2( 1 , 0 , adj, hs); int count = 0 ; for ( int i = 1 ; i <= n; i++) { if (dp1[i] <= d && dp2[i] <= d) { count++; } } return count; } // Function to traverse through edges int dfs1( int node, int par, List<List<Integer> > adj, HashSet<Integer> hs) { if (hs.contains(node)) { dp1[node] = 0 ; } for ( int ngr : adj.get(node)) { if (ngr != par) { int dis = dfs1(ngr, node, adj, hs); if (dis != - 1 ) { dp1[node] = Math.max(dp1[node], 1 + dis); } } } return dp1[node]; } // Function to traverse through edges void dfs2( int node, int par, List<List<Integer> > adj, HashSet<Integer> hs) { int max1 = - 1 , max2 = - 1 ; for ( int ngr : adj.get(node)) { if (ngr != par) { if (dp1[ngr] > max1) { max2 = max1; max1 = dp1[ngr]; } else if (dp1[ngr] > max2) { max2 = dp1[ngr]; } } } for ( int ngr : adj.get(node)) { if (ngr != par) { int dist = (dp1[ngr] == max1) ? max2 : max1; if (dist != - 1 ) { dp2[ngr] = dist + 2 ; } if (dp2[node] != - 1 ) { dp2[ngr] = Math.max(dp2[ngr], 1 + dp2[node]); } if (hs.contains(ngr)) { dp2[ngr] = Math.max(dp2[ngr], 0 ); } dfs2(ngr, node, adj, hs); } } } } class GFG { public static void main(String[] args) { int n = 7 , m = 2 , loudness = 3 ; List<Integer> canBeHeardFrom = Arrays.asList( 3 , 5 ); List<List<Integer> > edges = new ArrayList<>(); edges.add(Arrays.asList( 1 , 2 )); edges.add(Arrays.asList( 1 , 3 )); edges.add(Arrays.asList( 2 , 4 )); edges.add(Arrays.asList( 2 , 5 )); edges.add(Arrays.asList( 3 , 6 )); edges.add(Arrays.asList( 3 , 7 )); Solution obj = new Solution(); // Function call int res = obj.findAnnouncementNodes( n, m, canBeHeardFrom, loudness, edges); System.out.println(res); } } // This code is contributed by lokesh. |
Python3
from typing import List class Solution: def __init__( self ): # Initialising of dp vectors self .dp1 = [] self .dp2 = [] def findAnnouncementNodes( self , n: int , m: int , canBeHeardFrom: List [ int ], d: int , edges: List [ List [ int ]]) - > int : adj = [[] for i in range (n + 5 )] hs = set (canBeHeardFrom) for e in edges: adj[e[ 0 ]].append(e[ 1 ]) adj[e[ 1 ]].append(e[ 0 ]) # Resizing vectors self .dp1 = [ - 1 ] * (n + 5 ) self .dp2 = [ - 1 ] * (n + 5 ) # Traversing through dfs self .dfs1( 1 , 0 , adj, hs) if 1 in hs: self .dp2[ 1 ] = 0 # Traversing through dfs self .dfs2( 1 , 0 , adj, hs) count = 0 for i in range ( 1 , n + 1 ): if self .dp1[i] < = d and self .dp2[i] < = d: count + = 1 return count # Function to traverse through edges def dfs2( self , node: int , par: int , adj: List [ int ], hs: set ): max1 = max2 = - 1 for ngr in adj[node]: if ngr ! = par: if self .dp1[ngr] > max1: max2 = max1 max1 = self .dp1[ngr] elif self .dp1[ngr] > max2: max2 = self .dp1[ngr] for ngr in adj[node]: if ngr ! = par: dist = max2 if self .dp1[ngr] = = max1 else max1 if dist ! = - 1 : self .dp2[ngr] = dist + 2 if self .dp2[node] ! = - 1 : self .dp2[ngr] = max ( self .dp2[ngr], 1 + self .dp2[node]) if ngr in hs: self .dp2[ngr] = max ( self .dp2[ngr], 0 ) self .dfs2(ngr, node, adj, hs) # Function to traverse through edges def dfs1( self , node: int , par: int , adj: List [ int ], hs: set ) - > int : if node in hs: self .dp1[node] = 0 for ngr in adj[node]: if ngr ! = par: dis = self .dfs1(ngr, node, adj, hs) if dis ! = - 1 : self .dp1[node] = max ( self .dp1[node], 1 + dis) return self .dp1[node] # Driver code if __name__ = = "__main__" : n, m, loudness = 7 , 2 , 3 canBeHeardFrom = [ 3 , 5 ] edges = [[ 1 , 2 ], [ 1 , 3 ], [ 2 , 4 ], [ 2 , 5 ], [ 3 , 6 ], [ 3 , 7 ]] obj = Solution() # Function call res = obj.findAnnouncementNodes(n, m, canBeHeardFrom, loudness, edges) print (res) |
C#
// C# code for the above approach using System; using System.Collections.Generic; public class Solution { // Initialising of dp vectors List< int > dp1 = new List< int >(); List< int > dp2 = new List< int >(); public int FindAnnouncementNodes( int n, int m, List< int > canBeHeardFrom, int d, List<List< int > > edges) { List<List< int > > adj = new List<List< int > >(); HashSet< int > hs = new HashSet< int >(); foreach ( int x in canBeHeardFrom) hs.Add(x); for ( int i = 0; i <= n + 4; i++) { adj.Add( new List< int >()); dp1.Add(-1); dp2.Add(-1); } for ( int i = 0; i < edges.Count; i++) { int u = edges[i][0], v = edges[i][1]; adj[u].Add(v); adj[v].Add(u); } // Traversing through dfs dfs1(1, 0, adj, hs); if (hs.Contains(1)) dp2[1] = 0; // Traversing through dfs dfs2(1, 0, adj, hs); int count = 0; for ( int i = 1; i <= n; i++) if (dp1[i] <= d && dp2[i] <= d) count++; return count; } // Function to traverse through edges void dfs2( int node, int par, List<List< int > > adj, HashSet< int > hs) { int max1 = -1, max2 = -1; foreach ( int ngr in adj[node]) { if (ngr != par) { if (dp1[ngr] > max1) { max2 = max1; max1 = dp1[ngr]; } else if (dp1[ngr] > max2) { max2 = dp1[ngr]; } } } foreach ( int ngr in adj[node]) { if (ngr != par) { int dist = (dp1[ngr] == max1 ? max2 : max1); if (dist != -1) dp2[ngr] = dist + 2; if (dp2[node] != -1) { dp2[ngr] = Math.Max(dp2[ngr], 1 + dp2[node]); } if (hs.Contains(ngr)) dp2[ngr] = Math.Max(dp2[ngr], 0); dfs2(ngr, node, adj, hs); } } } // Function to traverse through edges int dfs1( int node, int par, List<List< int > > adj, HashSet< int > hs) { if (hs.Contains(node)) dp1[node] = 0; foreach ( int ngr in adj[node]) { if (ngr != par) { int dis = dfs1(ngr, node, adj, hs); if (dis != -1) dp1[node] = Math.Max(dp1[node], 1 + dis); } } return dp1[node]; } } public class GFG { // Driver's code static void Main( string [] args) { int n = 7, m = 2, loudness = 3; List< int > canBeHeardFrom = new List< int > { 3, 5 }; List<List< int >> edges = new List<List< int >> { new List< int > { 1, 2 }, new List< int > { 1, 3 }, new List< int > { 2, 4 }, new List< int > { 2, 5 }, new List< int > { 3, 6 }, new List< int > { 3, 7 } }; Solution obj = new Solution(); // Function call int res = obj.FindAnnouncementNodes(n, m, canBeHeardFrom, loudness, edges); Console.WriteLine(res); } } |
Javascript
class Solution { constructor() { this .dp1 = new Array(100005).fill(-1); this .dp2 = new Array(100005).fill(-1); } findAnnouncementNodes(n, m, canBeHeardFrom, d, edges) { const adj = Array.from({ length: n + 5 }, () => []); const hs = new Set(canBeHeardFrom); for (const [u, v] of edges) { adj[u].push(v); adj[v].push(u); } this .dfs1(1, 0, adj, hs); if (hs.has(1)) { this .dp2[1] = 0; } this .dfs2(1, 0, adj, hs); let count = 0; for (let i = 1; i <= n; i++) { if ( this .dp1[i] <= d && this .dp2[i] <= d) { count++; } } return count; } dfs1(node, par, adj, hs) { if (hs.has(node)) { this .dp1[node] = 0; } for (const ngr of adj[node]) { if (ngr !== par) { const dis = this .dfs1(ngr, node, adj, hs); if (dis !== -1) { this .dp1[node] = Math.max( this .dp1[node], 1 + dis); } } } return this .dp1[node]; } dfs2(node, par, adj, hs) { let max1 = -1, max2 = -1; for (const ngr of adj[node]) { if (ngr !== par) { if ( this .dp1[ngr] > max1) { max2 = max1; max1 = this .dp1[ngr]; } else if ( this .dp1[ngr] > max2) { max2 = this .dp1[ngr]; } } } for (const ngr of adj[node]) { if (ngr !== par) { const dist = this .dp1[ngr] === max1 ? max2 : max1; if (dist !== -1) { this .dp2[ngr] = dist + 2; } if ( this .dp2[node] !== -1) { this .dp2[ngr] = Math.max( this .dp2[ngr], 1 + this .dp2[node]); } if (hs.has(ngr)) { this .dp2[ngr] = Math.max( this .dp2[ngr], 0); } this .dfs2(ngr, node, adj, hs); } } } } const n = 7, m = 2, loudness = 3; const canBeHeardFrom = [3, 5]; const edges = [ [1, 2], [1, 3], [2, 4], [2, 5], [3, 6], [3, 7] ]; const obj = new Solution(); const res = obj.findAnnouncementNodes(n, m, canBeHeardFrom, loudness, edges); console.log(res); |
5
Time Complexity: O(V)
Auxiliary Space: O(V)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!