data-structures-for-disjoint-sets

Union-find structures maintain partition invariants by grouping elements into disjoint sets using MAKE-SET, FIND-SET, and UNION operations, ensuring each element belongs to exactly one set and connectivity queries are answered efficiently.

The amortized complexity of disjoint-set operations with path compression and union-by-rank is bounded by the inverse-Ackermann function, providing near-constant time per operation across long sequences of unions and finds.

Apply union-find to offline algorithms by processing queries or elements in reverse order, using UNION operations to merge sets and FIND-SET to locate representatives, enabling efficient offline minimum and Tarjan offline LCA computation.

Forest representations with union-by-rank and path compression outperform linked list representations for disjoint sets, achieving inverse-Ackermann amortized bounds instead of linear time, making forests better for large-scale connectivity problems.

Use disjoint-set data structures for incremental connectivity problems when edges are only added and you need to answer connectivity queries efficiently, as DSU provides near-constant amortized time per union and find operation.