aman_naughty's blog

Help in DSU Problem
By aman_naughty, history, 6 years ago, In English

Problem : problem

My code : code

Why is my DSU solution failing on test 14. Am I applying wrong logic Please help

  • Vote: I like it
  • -7
  • Vote: I do not like it

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

It is not necessary that the a[i] will hold the actual value of the root for every node. You need to use root(i) to get the root node. See your solution AC Here.

The only difference is finding the actual root for a node i.

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

    Why does A[i] not hold the actual value of the root?

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Initially, a[i] (From now on parent) just points to itself.

      During merging, The parent of the root of the set with the smaller size ( count of nodes in it) is changed to the root of the set with the larger size. ( We don't change the parent of all the nodes in the smaller sized state hence they do not always hold the correct value of root. )

      During querying for root, the parent of those nodes which lie on the path to the root of that queried node will be changed to root. ( All the nodes on the path to root will have the parent as root now.) ( This is called path compression if you don't do this then the query will just return the root and won't change any parent.) Btw, In your code, you have used path compression.

      tl;dr A[i] always holds the correct root value for the root nodes only. If you want A[i]'s to hold the correct value then apply queries to all the leaf nodes.

      → Reply