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

Автор 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.