New update is available. Click here to update.

Count Nodes within K-distance

Posted: 28 Dec, 2020
Difficulty: Hard


Try Problem

You are given a connected, undirected and acyclic graph with some of the nodes as marked and a positive number 'K'. You need to return the count of all such nodes which have a distance from all marked nodes less than 'K', which means every node whose distance from all marked nodes is less than 'K', should be counted in the result.

A graph is said to be connected if there is a path between every pair of vertex, i.e., from every vertex to any other vertex, there should be some path to traverse and acyclic means that the graph does not contain cycle and undirected means that the edge is bidirectional and one can move in both directions.


Marked Nodes are Circled with red colour.

Now consider this example of the graph. Here nodes 1,2, and 4 are marked, and let us take the value of K as 3, i.e., we have to find all the nodes at a distance less than 3 from all the marked nodes. We can see that nodes with index 5,9,8,2,0,7 have distances less than 3 from all marked nodes; therefore, the total count of nodes will be 6.
Input format :
The first line contains two space-separated integers 'V' and 'E', denoting the number of vertices and edges in the graph.

The next 'E' lines contain two space-separated integers denoting the vertices between whom edges exist.

The next line contains a single integer 'K' denoting the distance.

The next line contains a single integer 'M' representing the number of marked nodes in the graph.

The next line contains 'M' space-separated integers representing marked nodes.
Output format :
For each test case, print an integer denoting the count of the nodes which are less than 'K' distance from all the marked nodes.

The output of every test case will be printed in a separate line. 
You don’t have to print anything, it has already been taken care of. Just implement the given function. 
1 <= 'V' <= 10^4
0 <= 'E' <= 10^4
1 <= |'V'| <= 'V'
1 <= 'K' <= 35000
1 <= 'M' <= 7000

Time Limit: 1 sec.