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 :(
I'm not sure about what you mean by the case of repetition, could you explain it in detail?
Constraints please.
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|$$$