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

Автор mrkam, 12 лет назад, По-английски

If we define spar[v]=the number of nodes that node v is their parent in DSU how can we calculate it?

Теги dsu
  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
12 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

did you mean the parent-most node is v or v could be an intermediate parent ?

»
12 лет назад, скрыть # |
 
Проголосовать: нравится +13 Проголосовать: не нравится

That depends on the rest of your implementation. Usually for best performance you need size anyway to join smaller set to the bigger one, so size of the set is part of DSU internal data.

my DSU implementation. In order to get the size of the component which contains v you call dsu.size[dsu.update(v)]

»
12 лет назад, скрыть # |
 
Проголосовать: нравится +3 Проголосовать: не нравится

I need only one array to store both parent and size of sets. This is my DSU implementation.