size of components in DSU

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

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

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

dsu

mrkam
9 лет назад
5

Комментарии (5)

Написать комментарий?

rawbear1826

9 лет назад, # |

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

→ Ответить

mrkam

9 лет назад, # ^ |

The parent-most node if v

→ Ответить

rawbear1826

9 лет назад, # ^ |

← Rev. 2 →

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;

→ Ответить

marat.snowbear

9 лет назад, # |

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

→ Ответить