Sum of Distance

Hard

0/120

Average time to solve is 25m

Contributed by

10 upvotes

Asked in companies

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1

Sample Output 1

6 8 8 5 9
2 3 3

For first test-case the graph will be :-

The distance between 0 and 1 is 2
Distance between 0 and 2 is 2
Distance between 0 and 4 and 0 and 3 is 1
So ans[0]=2+2+1+1=6
Similarly, it can be calculated for others.

Sample Input 2

Sample Output 2

8 10 10 6 12 10 
1 1

Hint 1

Hint 2

Use bfs/dfs from each vertex to find the distance from all vertices.

Approaches (2)

Approach 1

Approach 2

Brute Force

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.

Time Complexity

O(N^2), where ‘N’ is the number of given nodes.

We run a dfs/bfs from every vertex.The bfs/dfs traversal takes O(n) time. Thus total time complexity is O(N^2).

Space Complexity

O(N), where ‘N’ is the number of given nodes.

In every dfs/bfs traversal we create distance array of size n which stores distance. Thus space complexity is O(N).

(100% EXP penalty)

Sum of Distance

Console