Fype's blog

DSU Struct
By Fype, 5 years ago, In English

Hello again :D

Here is my DSU struct in c++ because there isn't any in codeforces. I added some features like making a DSU equal to another or clearing DSU.

use it like :

DSU tmp(n);

Any suggestion comment below :D

UPD1 : I added more features

UPD2 : Now you can merge two DSUs. (like if you want to add every edge in graph A to graph B) https://paste.ubuntu.com/p/Xz3BNBGcN4/

  • Vote: I like it
  • +19
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it +6 Vote: I do not like it

clear method doesn't reset SetCnt variable. Also second constructor doesn't copy same variable.

→ Reply
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it
  1. You don't need custom copy-constructor, default one works fine here
  2. Strange naming of class fields, you have capitalized and non-capitalized names
  3. (p1 == p2? false: (par[p1] = p2) | 1) WHY? It doesn't make your code faster, just write it normally in 2-3 lines.
  4. Why size() returns a number of sets? Many people would expect that it would return a number of elements. Probably create separate methods for size and number of components
  5. Add rank heuristic
→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    Thanks for your suggestion. I will make it better

    it's better now i think:)

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

      You can just swap them if (sz[p1] < sz[p2])

      → Reply
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

In the case of calling set_union and both nodes have the same root, you will double the size of that component in sz[p1] += sz[p2], please fix that.

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

It's rather redundant to use const int & in the constructor. Just use const int without reference. It's faster and also more logical. Also, try to avoid using variable names that start with capital letters.

→ Reply