= Snapshot representatives before quick-find union
When merging two blocks in <quick-find>, let $a=rep_0(x)$ and $b=rep_0(y)$ be fixed saved labels. Replacing every old occurrence of $b$ by $a$ preserves all other blocks. A scan <loop invariant> says processed cells already have their specified final labels while unprocessed cells still have their old labels. Recomputing $rep(y)$ during this mutation can change the replacement label after the cell for $y$ is processed, causing remaining old-$b$ cells to be missed. Saving both labels makes the update criterion stable and the invariant provable.
Back to article page
