Last Updated: 11 Mar, 2021

Sum of Distance

Hard

Asked in companies

Solve now

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.

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

Solve now

Approaches

01 Approach

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.

Solve now

02 Approach

The main idea is we will find sum of the distance between parent and all the nodes in the subtree of parent.. Also we will find a number of children of every parent.Then we will find the answer for every child using the parent’s answer such that ANS[j]=ANS[i]-SUBTREE[j]+(N-2-SUBTREE[j]).

(N-2-SUBTREE[j] means excluding the children count of j).

Algorithm:

First run a dfs from any node and find the sum of distance of parent with all the nodes present in the SUBTREE of parent such that ANS[i]+=ANS[j]+SUBTREE[j] for all ‘j’ from 0 to N1 where N1 is the number of children of ‘i’.Also find the size of subtree such that SUBTREE[i]+=SUBTREE[j] for all ‘j’ from 0 to ‘N1’ where ‘N1’.After this increase the size of SUBTREE[i] by 1 (To include itself).
Then in second dfs find the answer for all the nodes using this ANS[j]=ANS[i]-SUBTREE[j]+(N-2-SUBTREE[j]).
In the end return the ‘ANS’ list.

Solve now