Блог пользователя aman_naughty

Help in DSU Problem
Автор aman_naughty, история, 6 лет назад, По-английски

Problem : problem

My code : code

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

  • Проголосовать: нравится
  • -7
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      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.

      → Ответить