da.2396's blog

Disjoint set union doubt!
By da.2396, history, 8 years ago, In English

so the ques is

and on this test case 30 29 2 1 3 2 4 3 5 2 6 4 7 4 8 1 9 5 10 4 11 4 12 8 13 2 14 2 15 8 16 10 17 1 18 17 19 18 20 4 21 15 22 20 23 2 24 12 25 21 26 17 27 5 28 27 29 4 30 25

my ans is 11 but they are showing 15 . Is there any possibility of ans > 11 ! Here is the link to tree

Tags dsu
  • Vote: I like it
  • -22
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It's very difficult to figure out the solution for the tree you are providing. Can you please explain the approach you used?

In general it's hardly the case that the problem setters have messed up the testcases. If they are showing 15 as the answer that is because 15 is probably the correct answer.

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It's impossible, ans can't be 15. Every removed edge creates a new tree. 15 removals will result in 16 trees. How could 30 nodes be divided in 16 trees with >= 2 nodes each?

→ Reply