mrkam's blog

size of components in DSU

By mrkam, 10 years ago, In English

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

Tags dsu
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

    The parent-most node if v

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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;
      → Reply
»
10 years ago, # |
  Vote: I like it +13 Vote: I do not like it

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)]

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

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

→ Reply