When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

astral_projected's blog

By astral_projected, history, 3 years ago, In English

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

| Write comment?
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I'm not sure about what you mean by the case of repetition, could you explain it in detail?

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Constraints please.

»
3 years ago, # |
Rev. 2   Vote: I like it +15 Vote: I do not like it

Is the graph connected?

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

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +15 Vote: I do not like it

      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.

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        How can a tree be disconnected

        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it +15 Vote: I do not like it

          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|$$$