Opening your learning space
Starting the app …
Opening your learning space
Starting the app …
Union–Find maintains a partition into disjoint sets and supports finding a representative and merging sets.
Free to browse · flashcards or a multiple-choice quiz · import from Essential
Formula
n is element count; operation counts and inverse Ackermann α(n) are dimensionless
| Symbol | Meaning | Unit |
|---|---|---|
| Representative of x’s set | element identifier | |
| Merge sets containing x and y | set operation | |
| Number of elements | count | |
| Inverse Ackermann function | dimensionless |
\text{find}(x)=\text{representative}(x),\quad \text{union}(x,y): S_x\cup S_yWith union by rank or size and path compression, m operations on n elements take O(m α(n)) time in the standard analysis. This is near constant, not literally O(1). The structure handles merging partitions, not arbitrary deletion or splitting. A representative is an internal identifier and need not be the smallest element.
With union by rank or size and path compression, m operations on n elements take O(m α(n)) time in the standard analysis. This is near constant, not literally O(1). The structure handles merging partitions, not arbitrary deletion or splitting. A representative is an internal identifier and need not be the smallest element.
Union–Find maintains a partition into disjoint sets and supports finding a representative and merging sets.
Compare set representatives
The equivalence assumes all unions were applied to the same structure.
Use the example for Union–Find (disjoint-set union) to explain which inputs determine the requested output.
The example connects concrete inputs to its result.
Union–Find maintains a partition into disjoint sets and supports finding a representative and merging sets.
The relation applies only under its stated assumptions.
Applying the relation to a different case without checking its stated assumptions.
Check the validity range before substituting values: With union by rank or size and path compression, m operations on n elements take O(m α(n)) time in the standard analysis. This is near constant, not literally O(1). The.
Formula cluster
Union–Find maintains a partition into disjoint sets and supports finding a representative and merging sets.
Start with {a},{b},{c},{d}. After union(a,b) and union(c,d), each pair shares a representative but the pairs differ. Then union(b,c) merges the components, so all four find operations return the same representative.
Maintain graph components, Kruskal’s minimum spanning tree and equivalence classes.
Here is how to work through a typical Union–Find (disjoint-set union) (Find a representative; merge sets) task step by step:
Task
Use the example for Union–Find (disjoint-set union) to explain which inputs determine the requested output.
Solution path
The example connects concrete inputs to its result.
Union–Find maintains a partition into disjoint sets and supports finding a representative and merging sets.
The relation applies only under its stated assumptions.
MAKE-SET creates a singleton component. FIND(x) returns the internal representative of x’s component. UNION(x,y) merges the components if they differ. Together they maintain an equivalence relation as pairs become connected. They do not return shortest paths or maintain sorted members; those need other structures. The near-constant bound requires union by rank or size and path compression. State supported operations and do not treat a representative as a canonical label. Additional data structures are needed to retrieve set contents or concrete paths. A separate component label can be stored when a stable domain name is required.
Union by rank or size attaches a shallower tree below a deeper one, limiting height. Path compression makes nodes visited by FIND point closer to the root. Together, m operations on n elements take O(m α(n)) amortized. The inverse Ackermann function grows extremely slowly, but it is not literally constant. The near-constant bound requires union by rank or size and path compression. State supported operations and do not treat a representative as a canonical label. Rank remains an upper estimate of height; it is not the total number of nodes. After compression, rank may remain an upper bound; it need not equal the current exact height.
No. The guarantee is amortized over a sequence, conventionally O(α(n)) per operation across that sequence. One FIND may traverse several parent links before compression. Calling it constant time is practical shorthand, not the formal bound for algorithm analysis. The near-constant bound requires union by rank or size and path compression. State supported operations and do not treat a representative as a canonical label. The actual duration of one operation still depends on the current tree shape. The formal guarantee concerns a sequence and does not rule out a longer individual FIND.
The standard structure supports merges, not arbitrary deletions or splits. After components are united, the parent forest does not retain enough information to undo every merge cheaply. Problems with dynamic connectivity and edge deletions need a specialized offline or fully dynamic method; ordinary Union–Find is not reversible. The near-constant bound requires union by rank or size and path compression. State supported operations and do not treat a representative as a canonical label. Rollback variants explicitly record changes and often restrict path compression. Rollback records changes, but does not automatically support arbitrary component splits.
Kruskal processes edges in nondecreasing weight. Before accepting edge (u,v), it checks whether FIND(u) and FIND(v) differ. If so, the edge joins components without making a cycle and UNION merges them. This structure supplies the connectivity test; it does not select weights or prove the greedy theorem itself. The near-constant bound requires union by rank or size and path compression. State supported operations and do not treat a representative as a canonical label. Edge sorting and the Union–Find test therefore serve different purposes in the algorithm. The minimum-spanning-tree proof is logically separate from the component-query data structure.
Quanta exam set
Curated exam set for "Union–Find (disjoint-set union)":
Question (front)
Which formula describes Union–Find (disjoint-set union)?
Answer in your set
Question (front)
How do you rearrange Union–Find (disjoint-set union) for Compare set representatives?
Answer in your set
Question (front)
Which common mistake happens with Union–Find (disjoint-set union)?
Answer in your set
+ 7 more cards: units, variables, derivation, example, exam task
The formula set contains 10 cards. After importing, review them and start practicing; your ratings determine later review intervals.
This list names subject references and further reading. A page or section number appears when it is part of the reference; these are not verbatim quotations.
Create a curated FSRS exam set for Find a representative; merge sets: formula recall, variables, derivation, rearrangement, worked example, common mistakes and exam context.
Curated formula set · LaTeX · FSRS spaced repetition · import from Essential