Unit 3.5 · about 3 h
108 / 324Union-find with path compression and union by rank
Connectivity queries that interleave with edge insertions defeat repeated traversal: each BFS costs a full scan while each union-find operation costs effectively constant time.
- implement
You can now
- Implement union-find with path compression and union by rank or size, and state the amortized inverse-Ackermann bound with its source.
- Identify when union-find cannot help: deletions, directed reachability and queries that need paths, not just connectivity.
- Choose the online union-find framing over one-shot BFS or DFS when edges arrive interleaved with queries.
Covers
- Union-find, path compression and union by rank or size
Study, in this order
2 steps
- Union-Find: parent forests, path compression, and union by rankDSA Handbook - graphs
The forest, the find, the union; Two heuristics that change the bound; Putting it all together (LC 684); LC 990: equality and inequality, two passes
Depth · Skim LC 685's directed case-split on first pass; return after the MST unit if directed redundancy still bites.
- Disjoint Sets, Lecture Note 11Algorithms - graph chapters
11.1 Reversed Trees (union by depth or rank, and the size-at-least-2-to-the-rank property); 11.3 Path Compression; 11.6 The Ackermann Function and its Inverse for the bound. Skim 11.2 Shallow Threaded Trees.
Focus on
- Compare
find(x)withfind(y), neverparent[x]withparent[y]: cousins share a root through a chain while their immediate parents differ. - Rank is an upper bound on height, not the height: compression shrinks trees without lowering ranks, and the size-at-least-2-to-the-rank property is what the log bound leans on.
- Count components as the set of
find(i)over all \(i\), never as the set ofparententries: stale intermediate pointers undercount. - Process all equalities before any inequality (LC 990): input order lies, because a later union can connect an earlier checked pair.
Reproduce closed-book
[[1,2],[1,3],[2,3]] and return [2,3] as the first redundant edge. Then union the chain 0-1 through 6-7 in order with union by rank and report maximum depth 1.Traps
- Rank without compression, or compression without rank: the adversarial chain
union(0,1),union(1,2), ... builds depth \(n\) when attachment is one-sided, and compression never fires before the firstfind. - Recursive
findon production-size chains: fine at LC 684 scale (\(n \le 1000\)), but the recursive form costs a frame per hop. Ship the iterative two-pass form past \(10^{5}\) elements. - String keys without make-set: integer constructors pre-fill every root, but email-keyed maps need an explicit make on first sighting or
findraisesKeyError.
Practice
LeetCode 684: Redundant Connection
Examples 1 ([[1,2],[1,3],[2,3]] answers [2,3]) and 2 (five-edge graph)
The first union returning False is the answer. After-attempt reference is the DSA Handbook 8.8 worked example and trace.
LeetCode 990: Satisfiability of Equality Equations
The two listed examples (a==b with b!=a answers False; the satisfiable set answers True)
Two passes: unions first, inequality checks second. After-attempt reference is the LC 990 section of DSA Handbook 8.8.
Self-test
-
Derive the \(O(\log n)\) bound for union by rank alone.
A rank-\(r\) root has at least \(2^r\) descendants (equal-rank merges double the set), so a tree on \(n\) nodes has rank at most \(\log_2 n\), and find walks at most that many parent pointers. -
Why do two passes decide LC 990 correctly?
Pass one builds every equivalence class the equalities force. Pass two checks each inequality against the final partition: any same-set inequality contradicts the input, and no order dependence remains because all unions precede all checks. -
Give two queries union-find cannot answer.
Deletions (parent pointers only merge; splitting needs a rebuild) and directed reachability or path queries (roots record connectivity, not direction or routes). -
What does \(\alpha(n) \le 4\) mean in practice?
Tarjan's bound says \(m\) operations cost \(O(m \times \alpha(n))\); \(\alpha\) stays at most 4 for any storable \(n\), so every operation is effectively constant, and the 1979 lower bound says no pointer-machine structure beats it.
Completion criterion
Stop when
Your blank-file DSU prints [2,3] on the redundant input with max chain depth 1, and LC 684 plus LC 990 pass with roots compared, never parents.
Leads to
- 3.7 Minimum spanning trees with Kruskal and Prim Union-find becomes Kruskal's cycle check: sort edges, accept across components.
- 3.8 Graph certificates and exhaustive small-graph validation Component counts need the find-then-count discipline, which the validation unit turns into checkers.
Comes after
- 3.3 DFS, cycle detection and bipartite testingMeet the other cycle-detection engine, for edges that arrive one at a time.
Resources for this unit
- DSA Handbook - graphs Study all of Part 8 in order. For each algorithm, write the representation, invariant, forbidden input assumptions and independently checkable output before reading the implementation.
- Algorithms - graph chapters Use the basic graph, depth-first search, minimum spanning tree, shortest path and flow chapters, and lecture note 11 Disjoint Sets for union-find, for correctness proofs and counterexamples to tempting wrong algorithms.
Also in this section
- AlgoMaster DSA - graph slice Attempt Number of Islands, Course Schedule II and Network Delay Time cold. They cover traversal, dependency modeling and weighted shortest paths; add one narrative problem only if graph modeling remains weak.
- Hypothesis - generated graph tests Generate small sparse, dense, disconnected, cyclic, parallel-edge and weighted graphs. Compare optimized results with exhaustive or deliberately simple references and retain shrunk failures.
- NeetCode - unseen graph problems Use two unseen story problems without graph tags. Grade the model, assumptions, certificate and tests as well as the final answer.