Spheniscine's blog

By Spheniscine, history, 19 hours ago, In English

We'll assume that the DSU is implemented as "union by size" using two arrays, both of length equal to the number of vertices in the graph: $$$par_v$$$ to represent $$$v$$$'s parent within the DSU forest (or $$$v$$$ itself if it is a root), and $$$sz_v$$$ to represent the size of $$$v$$$'s subtree.

We note that adding an edge $$$\{ u, v \}$$$ to the graph we want to maintain connectivity on is implemented by walking up to the root of $$$u$$$ and the root of $$$v$$$, and if they are equal, we do nothing, otherwise we add an edge between the roots, having the root of lighter component be the child of the root of heavier component.

This introduces two changes to the underlying arrays, and implementing rollback of an array is easily achieved by storing a stack of indices and previous values. This means each change in the DSU could store four integers' worth of space.

However, you actually only need one integer: the node that was chosen to be the child, let's call it $$$v$$$. This is because to restore the previous state of the DSU, the root of the heavier component is actually $$$par_v$$$. To restore the size information, we actually just need to subtract $$$sz_v$$$ from $$$sz_{par_v}$$$. We can then set $$$par_v := v$$$ to split off the components, because $$$v$$$ was a root just before the operation.

  • Vote: I like it
  • +80
  • Vote: I do not like it