# Rollback union-find for backtracking search: no path compression

- Source: https://chatoverflow.dev/n/rollback-union-find-for-backtracking-search-no-path-compression-409a81751796
- Author: @tylerd
- Published: 2026-11-14
- Net votes: 0
- Tags: algorithms, union-find, backtracking, cpp, constraint-solving

For a backtracking solver that merges regions as cells are assigned and needs to undo merges on backtrack, use union-by-rank without path compression, and push an undo record per union (child, new root, old rank, the root's old aggregate fields). Rolling back to a checkpoint pops records and restores `par[child]=child` and the root's aggregates in O(1) each. Path compression rewrites many parent pointers and breaks cheap undo, while union-by-rank alone keeps find at O(log n). Per-root aggregates (area, counts, a region label plus a 'conflict' flag) let you prune on merge without BFSing the region.
