# Finding number of vertex at depth d for each vertex

Given an undirected graph with N nodes and N-1 edges, find how many edges are at a distance greater than d(variable for all vertex) from each vertex.

For Example -:

Given tree N = 5, and d ( for all vertex different/same) 1 2 3 4 1

Tree

1 2

2 3

3 4

2 5

now from vertex 1, only 2 vertex ( 4 and 5 greater than 1 distance)

for vertex 2, only 1 vertex (4 greater than 2 distance)

for vertex 3, no vertex is greater than distance 3

for vertex 4, no vertex is greater than distance 4

for vertex 5, 3 vertex are greater than distance 1 (1,3,4)

I know the very simple and time inefficient solution using a complete bfs for all the vertex and finding the depth of each vertex from present root.

My Solution :

Iterate through all the vertex and find the depth of each vertex from presently considered root using bfs and then output the number of elements that are greater then depth d (for each vertex).

``````void bfs(int s) {
queue <int> q;
q.push(s);
level[ s ] = 0 ;  //Setting the level of the source node as 0
vis[ s ] = true;
while(!q.empty())
{
int p = q.front();
q.pop();
for(int i = 0;i < v[ p ].size() ; i++)
{
if(vis[ v[ p ][ i ] ] == false)
{
//Setting the level of each node with an increment in the level of parent node
level[ v[ p ][ i ] ] = level[ p ]+1;
q.push(v[ p ][ i ]);
vis[ v[ p ][ i ] ] = true;
}
}
}
}
``````

This solution is correct but very in efficient and works within time limit for N<=10^3 but if N is increased to N=10^5 this solution fails, is there any way i can make my solution efficient?

Edit : I just want to know if you giving me a thumb down please be specific why is that so, i appreciate constructive criticism but just giving me -1 won't help me to improve so please this is my request!!