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

DSU Struct
Автор Fype, 4 года назад, По-английски

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/

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

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

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

→ Ответить
»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
  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
→ Ответить
»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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.

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

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.

→ Ответить