Union-find (DSU): merging disjoint sets · 1 of 2
Union-find basics
Keep groups that only merge as trees in a parent array, and tell whether two elements are connected in a few steps with union by size and path compression.
- Disjoint Set Union Path compression and union by size or rank with their complexity, then many applications: per-set data, distances to the root, checking bipartiteness online and offline lowest common ancestors. cp-algorithms.com (opens in a new tab)
- Disjoint Set Union A short implementation with path compression, a solved focus problem and lists of standard and harder problems. usaco.guide (opens in a new tab)
- 并查集 (Disjoint set union) Path compression and union by size with a complexity discussion, then a DSU that supports deleting an element and weighted DSU, which stores an offset to the parent. oi-wiki.org (opens in a new tab)