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!!