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

size of components in DSU

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

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

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

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

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

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

    The parent-most node if v

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

      for all nodes (other than v) you check recursively if the parent of this node is v and increase the counter by 1

      // n       : number of nodes
// pset[i] : parent of node i
// cnt     : counter
int findSet(int i) { return (pset[i] == i) ? i : (pset[i] = findSet(pset[i])); }
for(int i = 0; i < n; i++)
  if(findSet(i) == v)
     cnt++;
spar[v] = cnt;
      → Ответить
»
10 лет назад, # |
  Проголосовать: нравится +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)]

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

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

→ Ответить