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 :(

Auto comment: topic has been updated by astral_projected (previous revision, new revision, compare).I'm not sure about what you mean by the case of repetition, could you explain it in detail?

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.

Constraints please.

I've updated the problem with constraints, pls have a look.

Auto comment: topic has been updated by astral_projected (previous revision, new revision, compare).Stuck at the same problem

Is the graph connected?

Also, do you have the link to the original problem?

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 :/

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.

How can a tree be disconnected

From the way you described the problem, there are no guarantees that the graph is a tree...

Take the following example:

N = 5

Edges = { (1, 2), (2, 4), (4, 5), (5, 1) }

The graph has two connected components and $$$|E| + 1 = |V|$$$

graph is connected and has n-1 edges and we need to find no. of ways to pick 3 nodes which are equidistant