Sum of Distance

Posted: 11 Mar, 2021
Difficulty: Hard

PROBLEM STATEMENT

Try Problem

You are given an undirected unweighted graph such that there are no loops in this graph and it is strongly connected and there are always (vertices-1) edges in the graph. For each node, you need to find the sum of the distance of all other nodes from the given node.

Distance between any two nodes is the number of edges between the two given nodes.

Input Format:
The first line of input contains an integer 'T', the number of test cases.

The first line of the test case contains a single integer ‘N’.

From the second line onwards next 'N-1' lines denote the edges of the graph.

Each edge is characterized by two integers  'A' and 'B' where 'A' and 'B' denote the endpoints of the edge. The edges[i][0], edges[i][1] contains the endpoints of edges.
Output Format:
For each test case, return the list where the ith element denotes the distance of the ith vertex from all others vertices.
Note:
You are not required to print the expected output; it has already been taken care of. Just implement the function.
Constraints
1 <= T <= 50
1 <= N <= 10^3
0 <= edges[i][0], edges[i][1] <= N-1  
Total number of edges = N-1

Time Limit: 1 sec
Approach 1

The key idea is to apply bfs/dfs from each vertex to find distance from all vertices.

 

Algorithm:

  • Create a list answer of size ‘N’ with default value 0.
  • Run a for loop from ‘i’ = 0 to ‘N’.Run a bfs from ith vertex such that it will give distance from ith vertex to other vertices.Such that DISTANCE[j] is the distance between ith vertex and jth vertex.
  • The ANSWER[i] is equal to sum of distance array.
  • Return the 'ANSWER' array.
Try Problem