Disjoint set union

In short

A disjoint-set union (DSU) or union-find structure maintains a partition of n elements into non-overlapping sets and supports two operations - find(x) (which set does x belong to) and union(a,b) (merge the two sets). It is the standard way to answer "are these two things already connected?" while connections keep arriving, which is why it sits inside Kruskal's minimum spanning tree algorithm, cycle detection in undirected graphs and connected-component labelling. With union by rank/size plus path compression, m operations on n elements cost O(m·α(n)), where α is the inverse Ackermann function and is at most 4 for any input that fits in a computer - effectively constant time. It is examined in GATE CS (programming and data structures, greedy algorithms/MST), in university data-structures and design-and-analysis-of-algorithms papers, and is a frequent coding-round question at Amazon India, Microsoft IDC, Google India, Flipkart, Zoho, Samsung R&D, Media.net and in TCS Digital/CodeVita-style contests.

Explained

What the structure is and what it must support

• A disjoint-set (partition) of a universe {0,1,…,n−1} is a family of sets that are pairwise disjoint and together cover the universe. Each set has one representative (also called leader or root).
• Operations in the standard ADT:
  1. make_set(x) / init(n) - start with n singleton sets, so n components.
  2. find(x) - return the representative of x's set; x and y are in the same set iff find(x) == find(y).
  3. union(a,b) (also unite/merge) - merge the sets containing a and b; a no-op if they already coincide.
  4. Optional: size(x), count() (number of components), connected(a,b).
• DSU models an equivalence relation built up incrementally: reflexive, symmetric, transitive. Each set is an equivalence class. This is exactly why it suits graph connectivity, where "connected to" is an equivalence relation on vertices.
• It is an incremental (semi-dynamic) structure: edges may be added, never removed. Deletion is not supported efficiently.

Representations, from naive to forest

• Quick-find (array of labels): label[x] stores the set id. find is O(1); union must relabel every member of one set, O(n). n−1 unions cost O(n²). Simple, and still used when finds hugely outnumber unions.
• Linked-list representation: each set is a list with a pointer to the representative; union concatenates lists but all nodes of one list need their representative pointer fixed - O(n) worst case. With weighted union (always append the smaller list to the larger), any element's pointer is updated at most log₂n times, giving O(n log n) for n unions - this is the *small-to-large* argument.
• Forest (tree) representation - the one that is used: parent[x]; a root satisfies parent[x] == x. find walks parent pointers up to the root; union makes one root the child of the other, so a union is O(1) once the roots are known.
• Quick-union without balancing is dangerous: uniting 1→2, 2→3, 3→4 … builds a path of length n−1, and each find becomes O(n). The two heuristics below fix this.

Heuristic 1 - union by rank or by size

• Union by size: attach the root of the smaller set under the root of the larger; keep sz[root]. Any element's depth increases only when its set at least doubles, so depth ≤ log₂n.
• Union by rank: keep an integer rank[root], an upper bound on tree height. Attach the lower-rank root under the higher-rank root; on a tie, attach either way and increment the winner's rank by 1.
• Key invariant: a tree whose root has rank r contains at least 2^r nodes (proved by induction - rank r is created only by merging two rank-(r−1) trees of ≥2^r−1 nodes each). Hence rank ≤ ⌊log₂n⌋ and find is O(log n) worst case even without compression.
• Union by size and union by rank both give O(log n); size is marginally easier to reason about and gives size() for free, rank uses one byte per node. Either is accepted in exams.

Heuristic 2 - path compression

• After find(x) has located the root r, make every node on the traversed path point directly to r. The next find on any of them is O(1).
• Variants, all O(α(n)) when combined with balancing:
  • Full path compression - two passes (or one recursive pass): all path nodes re-pointed to the root.
  • Path splitting - each node is re-pointed to its grandparent, one pass.
  • Path halving - every other node is re-pointed to its grandparent; the usual iterative one-liner p[x]=p[p[x]]; x=p[x]; - no recursion, so no stack overflow at n = 10⁶.
• After compression, rank is no longer the exact height - it remains a valid *upper bound*, which is all the analysis needs. Ranks of roots never decrease and never change during a find.
• Path compression alone (arbitrary union) is already good: amortized Θ(log n) per operation, more precisely Θ(n + f·log_(1+f/n) n) for f finds. Balancing alone is O(log n) worst case. Both together give the near-constant bound.

Complexity and the analysis, in outline

• Result (Tarjan, 1975): with union by rank and path compression, a sequence of m operations on n elements takes O(m·α(m,n)) time, where α is the inverse Ackermann function. Matching lower bound (Fredman–Saks 1989, Tarjan): Ω(m·α(n)) for any pointer-machine/cell-probe implementation - so the structure is optimal, and DSU is *not* strictly O(1) amortized.
• Why α is negligible: α(n) ≤ 4 for all n below a tower far larger than the number of atoms in the universe. The earlier Hopcroft–Ullman bound O(m log\* n) is easier to state and often enough in exams - log\* n (iterated logarithm) is 5 for n = 10⁶ and ≤ 5 for every practical n.
• Proof sketch (rank-block / partition argument): ranks strictly increase along any root-ward path. Partition ranks into blocks [r, 2^r). A find charges O(1) per block boundary crossed (that is O(log\* n) charges) and charges the remaining steps to the nodes themselves; each node can be charged only until its parent's rank leaves its block, and a node of rank r is re-pointed to a strictly higher-rank parent each time, bounding its total charge. Summing gives O((m+n) log\* n). Tarjan's sharper accounting replaces log\* with α.
• Space: 2n integers (parent + rank/size), i.e. 8 MB for n = 10⁶ with 32-bit ints. No pointers, no allocation - excellent cache behaviour, which is why DSU is fast in practice far beyond what the bound promises.

Variants and extensions commonly examined

• DSU with component data: store size, count, min/max, sum or an edge count at the root; merge in O(1) during union. Used for "size of the largest friend circle after each query".
• Weighted / potential DSU (DSU with offsets): store d[x] = value(x) − value(parent[x]); find accumulates offsets to the root. Answers "is the set of relations x − y = c consistent?" and relative-difference queries.
• Parity DSU / bipartiteness: offsets modulo 2, or the "DSU of size 2n" trick where x and x+n represent the two colours. An edge joining two vertices of equal parity proves an odd cycle, so the graph is not bipartite.
• DSU with rollback (undo): union by size/rank without path compression, pushing the changed cells on a stack; each union is O(log n) and can be undone in O(1). Needed for offline dynamic connectivity (divide-and-conquer over the time line) and for DSU-on-segment-tree problems.
• Persistent DSU: parent array in a persistent array/segment tree, O(log²n) per operation; answers queries about past versions.
• Small-to-large merging ("DSU on tree", sack): merge the smaller std::set/map into the larger; total O(n log n) element moves - the same weighted-union argument as above.
• Interval/next-pointer DSU: parent[i] points to the next unused index, giving amortized near-constant "paint this cell and jump to the next free one" sweeps.
• Limitations: no split or edge deletion; no enumeration of a set's members without extra lists; find is not O(1) worst case; not thread-safe without lock-free CAS variants (concurrent union-find is used in parallel connected-component labelling).

Classic algorithms built on DSU

• Kruskal's MST: sort E edges by weight, scan in order, accept an edge iff its endpoints are in different sets. Total O(E log E) - the sort dominates; the DSU part is O(E α(V)). Stop after V−1 accepted edges.
• Cycle detection in an undirected graph: scanning edges, the first edge whose endpoints already share a root closes a cycle. (For *directed* graphs DSU does not work - use DFS back-edges or Kahn's algorithm.)
• Connected components / number of provinces: components = n − (number of successful unions).
• Tarjan's offline LCA and offline range/ancestor queries; Edmonds' blossom algorithm, where union-find contracts blossoms.
• Connected-component labelling in image processing (two-pass algorithm resolves label equivalences with DSU); percolation and maze generation; Kruskal-based clustering (single-linkage).
• Note on syllabus: DSU is an algorithm, not an engineered artefact, so no BIS/IS code applies; what varies between universities is only whether it appears under "Data structures" or under "Greedy algorithms / MST" in the DAA paper - AICTE model curriculum and most CBCS schemes place it in both.

Key points

• Disjoint set - a partition of n elements; each class has one representative; find(x)==find(y) tests same-class membership.
• Forest representation - parent[] array, root is self-parent; union is O(1) after two finds.
• Union by size - smaller tree under larger; depth ≤ log₂n because a node's depth grows only when its set doubles.
• Union by rank - rank is an upper bound on height; rank increases only on a tie; a rank-r tree has ≥ 2^r nodes, so rank ≤ ⌊log₂n⌋.
• Path compression - re-point every node on the find path to the root; later finds on them are O(1).
• Path halving/splitting - one-pass iterative compression, no recursion, same asymptotics.
• Combined bound - O(m·α(n)) amortized; α(n) ≤ 4 for all realistic n; lower bound Ω(m·α(n)), so it is optimal but not truly constant.
• One heuristic only - rank alone O(log n) worst case; compression alone O(log n) amortized.
• Components count - starts at n, decreases by 1 per *successful* union; components = n − successful unions.
• Kruskal - sort edges then DSU-filter; O(E log E); accept exactly V−1 edges for a connected graph.
• Cycle test - an edge inside one set closes a cycle; valid for undirected graphs only.
• Weighted DSU - store offset to parent; supports "value(x) − value(y) = c" consistency checking.
• Parity DSU / 2n trick - detects odd cycles, i.e. non-bipartite graphs.
• Rollback DSU - no compression, union by size, undo in O(1); each operation O(log n).
• Small-to-large merging - merging the smaller container costs O(n log n) in total.
• No deletion - removing edges needs link-cut trees, Euler-tour trees, or offline divide-and-conquer with rollback.
• Space - 2n integers; cache-friendly, no dynamic allocation.

Formulas and examples

int p[N], sz[N], comps;
void init(int n){ comps=n; for(int i=0;i<n;i++){ p[i]=i; sz[i]=1; } }
int find(int x){ while(p[x]!=x){ p[x]=p[p[x]]; x=p[x]; } return x; }   // path halving
bool unite(int a,int b){
    a=find(a); b=find(b);
    if(a==b) return false;                 // same set -> this edge closes a cycle
    if(sz[a]<sz[b]) std::swap(a,b);        // union by size
    p[b]=a; sz[a]+=sz[b]; --comps;  return true;
}
// recursive full compression:  int find(int x){ return p[x]==x ? x : p[x]=find(p[x]); }
// weighted DSU:  int find(int x){ if(p[x]==x) return x; int r=find(p[x]); d[x]+=d[p[x]]; p[x]=r; return r; }

Example 1 - trace the parent array (typical GATE/university question). n = 8, elements 0…7, union by size (ties: second root attached under the first), path compression on find.

• Final array, index 0…7: parent = [0, 1, 1, 1, 1, 1, 5, 5].
• Successful unions = 6, so components = 8 − 6 = 2: {0} and {1,2,3,4,5,6,7}.
• Height is 2 (node 6 and 7 are at depth 2); a find(6) now would compress them to depth 1.

Example 2 - Kruskal's MST on a 6-city fibre network. Vertices A–F; edge costs in ₹ lakh. Edges: B-C 2, D-E 2, C-D 3, E-F 3, A-B 4, A-C 4, C-E 4, B-D 6, D-F 7 (already sorted).

• Accepted edges = 5 = V − 1, so the scan stops; MST cost = ₹14 lakh. C-E, B-D and D-F are never examined.
• DSU calls: 2 finds per edge × 6 edges examined = 12 finds, 5 unions.

Example 3 - why the heuristics matter, with numbers. n = 10⁶ elements, m = 5×10⁶ operations.

• Unbalanced quick-union, worst case: a chain of depth 10⁶ ⇒ up to 5×10⁶ × 10⁶ = 5×10¹² pointer steps - minutes to hours.
• Balancing only: depth ≤ ⌊log₂10⁶⌋ = 19 ⇒ ≤ 5×10⁶ × 19 ≈ 9.5×10⁷ steps.
• Balancing + compression: α(10⁶) ≤ 4 ⇒ ≈ 5×10⁶ × 4 = 2×10⁷ steps, well under a second in C++.
• Maximum possible rank = 19, because a rank-20 tree needs 2²⁰ = 1,048,576 > 10⁶ nodes.

Example 4 - weighted DSU consistency check (relative salaries, ₹). Statements, processed in order:

1. value(2) − value(1) = 500 - different roots → attach root 2 under root 1 with pot[2] = 500.
2. value(3) − value(2) = 300 - find(2) gives root 1 with pot 500 → attach 3 under 1 with pot[3] = 500 + 300 = 800.
3. Query value(3) − value(1): same root, pot[3] − pot[1] = 800 − 0 = ₹800 - consistent with the claim 800.
4. value(4) − value(1) = 200 → attach 4 under 1 with pot[4] = 200.
5. Claim value(4) = value(3) − 600: check pot[4] − pot[3] = 200 − 800 = −600 ✓ consistent.
6. Claim value(2) − value(3) = 100: pot[2] − pot[3] = 500 − 800 = −300 ≠ 100 → contradiction, statement rejected.

Example 5 - bipartite check with the 2n trick. Graph on {1,2,3} with edges (1,2), (2,3), (3,1); DSU over 6 nodes where i+3 is "opposite colour of i".

• Edge (1,2): union(1, 2+3=5) and union(1+3=4, 2). Sets: {1,5}, {2,4}.
• Edge (2,3): union(2, 6), union(5, 3) → {1,5,3}, {2,4,6}.
• Edge (3,1): check find(3) vs find(1) - both are in {1,5,3}, i.e. 3 and 1 are forced to the same colour while the edge demands different colours ⇒ odd cycle ⇒ not bipartite. (A triangle is indeed the smallest odd cycle.)

(*after the two finds)

Where it is used

• Network and infrastructure planning: Kruskal-based minimum spanning trees for optical-fibre and BharatNet-style rollouts, power distribution feeders and water pipeline layouts, where DSU decides whether a proposed link is redundant.
• Graph and database engineering: connected-component and clustering jobs (union-find is the single-machine method; Spark/GraphX's connectedComponents instead uses Pregel label propagation); entity resolution and de-duplication - merging customer or vendor records that share a phone/PAN/e-mail into one identity cluster, the standard "accounts merge" problem at Flipkart, Meesho, PhonePe and credit bureaus.
• Image processing and remote sensing: connected-component labelling in OCR, defect inspection on production lines, and segmentation of satellite imagery (ISRO/NRSC land-parcel and water-body extraction).
• Compilers and systems: register allocation and SSA phi-node coalescing (union-find over value classes), type inference/unification in language implementations, filesystem check (fsck) cycle checks.
• Competitive programming and hiring rounds: CodeChef/Codeforces graph problems, CodeVita, and DSA interviews at Amazon India, Microsoft IDC, Google India, Zoho, Samsung R&D and Media.net - "number of provinces", "redundant connection", "number of islands II", "accounts merge", "satisfiability of equality equations".
• Job roles: SDE and backend engineers writing graph/connectivity features, data engineers building record-linkage pipelines, quantitative/optimisation engineers in logistics and telecom network design.

Interview questions

• Q: What are the two core operations of DSU and what is their amortized cost? A: find(x) returns the representative and union(a,b) merges two sets; with union by rank/size and path compression, each costs O(α(n)) amortized, effectively constant since α(n) ≤ 4 for realistic n.
• Q: Why does union by rank alone guarantee O(log n)? A: A tree whose root has rank r contains at least 2^r nodes, so rank - and hence height - never exceeds ⌊log₂n⌋.
• Q: Does path compression change the meaning of rank? A: Yes - rank stops being the exact height and becomes an upper bound, which is still sufficient because unions only compare ranks and the analysis only needs monotonicity.
• Q: How do you detect a cycle in an undirected graph using DSU? A: Process edges one by one; if both endpoints already have the same root, that edge closes a cycle. For directed graphs this fails - use DFS back-edges or topological sorting.
• Q: How many components remain after a sequence of unions? A: n minus the number of *successful* unions; unions where both endpoints already share a root do not reduce the count.
• Q: Can DSU support deleting an edge? A: Not directly - it is incremental only. Use link-cut trees or Euler-tour trees for fully dynamic connectivity, or offline divide-and-conquer over time with a rollback DSU.
• Q: Why is rollback DSU implemented without path compression? A: Compression rewrites an unbounded number of cells per find, so it cannot be undone in O(1); union by size alone keeps each union's changes to two cells and still gives O(log n) per operation.
• Q: Is DSU O(1) amortized? A: No. Fredman–Saks and Tarjan proved a matching Ω(m·α(n)) lower bound for pointer-machine implementations, so O(m·α(n)) is optimal but not constant.
• Q: Where is DSU inside Kruskal's algorithm and what is the overall complexity? A: It tests whether an edge's endpoints are already connected; total cost is O(E log E) for the sort plus O(E·α(V)) for the DSU, so the sort dominates.
• Q: How would you check if a list of equations like x − y = 5 is consistent? A: Weighted DSU: store each node's offset to its parent, accumulate offsets during find, and when both variables already share a root verify that the stored difference equals the claimed one.
• Q: How do you test bipartiteness with DSU? A: Keep parity offsets mod 2 (or duplicate each vertex as "same/opposite"); an edge whose endpoints are forced into the same colour class reveals an odd cycle, so the graph is not bipartite.
• Q: Iterative or recursive find for n = 10⁶? A: Iterative with path halving - the recursive version can overflow the stack on a deep chain before the first compression happens, and halving gives the same asymptotic bound.

Common mistakes

• Calling union(a,b) on the raw elements without taking find of both first, or writing parent[b] = a instead of parent[find(b)] = find(a) - this corrupts the forest silently.
• Comparing a == b instead of find(a) == find(b) when testing connectivity, so an already-connected pair is accepted as a new edge and the component count goes wrong.
• Decrementing the component counter (or sz) even when the union was a no-op - every "number of components/islands after each query" answer then drifts.
• Using DSU for cycle detection in a directed graph, or for a graph where edges can be removed.
• Applying only one heuristic in a tight-time problem (compression without balancing, or rank without compression) and then quoting O(α(n)) for it.
• Forgetting to re-point the node to the returned root in weighted DSU, or adding the parent's offset *before* the recursive find has updated it - the order must be: recurse, then d[x] += d[p[x]], then p[x] = root.
• Off-by-one and indexing errors: 1-based problem input into a 0-based array, or sizing the array n instead of 2n for the bipartite/parity trick.

Related topics

• Graphs and their representation · Trees and binary search trees · Minimum spanning trees: Kruskal and Prim · Hashing and hash tables (for mapping names to indices) · Segment trees and Fenwick trees · Greedy algorithms and amortized analysis.