### astral_projected's blog

By astral_projected, history, 7 weeks ago,

Number of ways to choose 3 nodes in a graph such that all are equidistant from each other.

Note: Number of edges = Number of nodes -1

Example:

Input: [1,2] [1,3] [1,4] [1,5]

Constraints 2 < N <= 10^4

Output: 4

My approach:

1.Bfs from all nodes

2.ans += NC3 : N = number of nodes on same level.

Problem: Unable to handle case of repetition, Pls look into it and provide me a solution for the same. Ps: ive been stuck on this for a long time :(

• 0

 » 7 weeks ago, # |   0 Auto comment: topic has been updated by astral_projected (previous revision, new revision, compare).
 » 7 weeks ago, # |   0 I'm not sure about what you mean by the case of repetition, could you explain it in detail?
•  » » 7 weeks ago, # ^ |   0 Sorry for being unclear, I meant, Counting the same set of elements more than once. I can't think of a way to avoid it without using excessive memory.
 » 7 weeks ago, # |   0 Constraints please.
•  » » 7 weeks ago, # ^ |   0 I've updated the problem with constraints, pls have a look.
 » 7 weeks ago, # |   0 Auto comment: topic has been updated by astral_projected (previous revision, new revision, compare).
 » 6 weeks ago, # |   0 Stuck at the same problem
 » 6 weeks ago, # | ← Rev. 2 →   +15 Is the graph connected?Also, do you have the link to the original problem?
•  » » 6 weeks ago, # ^ |   0 Yes it is connected since the number of edges are 1 less than number of nodes. And sadly no, I got this problem in a contest to which i have no access now :/
•  » » » 6 weeks ago, # ^ |   +15 It is possible for a graph to be disconnected whilst having |E| + 1 = |V|, so unless it's explicit in the statement, you can't consider this to be true.
•  » » » » 6 weeks ago, # ^ |   0 How can a tree be disconnected
•  » » » » » 6 weeks ago, # ^ |   +15 From the way you described the problem, there are no guarantees that the graph is a tree...Take the following example:N = 5Edges = { (1, 2), (2, 4), (4, 5), (5, 1) }The graph has two connected components and $|E| + 1 = |V|$
•  » » » » » » 6 weeks ago, # ^ |   0 graph is connected and has n-1 edges and we need to find no. of ways to pick 3 nodes which are equidistant