Linked Questions

Popular Questions

Finding number of vertex at depth d for each vertex

Asked by At

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

Related Questions