astral_projected's blog

By astral_projected, history, 7 weeks 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 :(

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by astral_projected (previous revision, new revision, compare).

»
7 weeks 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?

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # |
  Vote: I like it 0 Vote: I do not like it

Constraints please.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by astral_projected (previous revision, new revision, compare).

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Stuck at the same problem

»
6 weeks 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?

  • »
    »
    6 weeks 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 :/

    • »
      »
      »
      6 weeks 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.

      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        How can a tree be disconnected

        • »
          »
          »
          »
          »
          6 weeks 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|$$$

          • »
            »
            »
            »
            »
            »
            6 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

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