Data Structures19 sections · 729 units
Open in Course

Persistent UF Applications

When you need it

Offline dynamic connectivity: Process edge insertions, then answer "were u and v connected after operation k?"

Rollback operations: Undo union operations by reverting to an earlier version.

Branching histories: Create different "timelines" from the same base state.

Comparison with Link-Cut trees:

  • Link-Cut: O(logn)O(\log n) amortized, supports cut
  • Persistent UF: O(logn)O(\log n) worst case, no cut support, version history

Use persistent UF when you need version queries but not edge deletion.