--- # === IDENTITY === id: software/patterns/union-find-disjoint-set/2026 canonical_question: "How do I implement and use Union-Find (Disjoint Set)?" aliases: - "Union-Find data structure implementation" - "Disjoint Set Union DSU algorithm" - "How to detect cycles with Union-Find" - "Kruskal MST with Union-Find" - "Connected components using Union-Find" - "Path compression and union by rank" entity_type: software_reference domain: software > patterns > union_find_disjoint_set region: global jurisdiction: global temporal_scope: 2020-2026 # === VERIFICATION === last_verified: 2026-02-24 confidence: 0.95 version: 1.0 first_published: 2026-02-24 # === TEMPORAL VALIDITY === temporal_validity: status: stable last_breaking_change: null next_review: 2026-08-23 change_sensitivity: low # === CONSTRAINTS === constraints: - "Union-Find only works on equivalence relations (reflexive, symmetric, transitive) -- does not support directed relationships" - "Cannot efficiently undo union operations -- use persistent/rollback variant if undo is required" - "Path compression makes the structure non-persistent -- parent pointers are mutated during find" - "Do not use Union-Find for shortest-path or weighted-edge queries -- it only tracks connectivity" - "Union by rank and union by size are mutually exclusive optimizations -- pick one, not both" # === SKIP CONDITIONS === skip_this_unit_if: - condition: "You need shortest path between two nodes" use_instead: "Use BFS (unweighted) or Dijkstra/Bellman-Ford (weighted)" - condition: "You need to enumerate all nodes in a connected component" use_instead: "Use BFS/DFS traversal on an adjacency list" - condition: "You need to remove edges or undo unions dynamically" use_instead: "Use link-cut trees or offline algorithms with rollback" # === AGENT HINTS === inputs_needed: - key: use_case question: "What problem are you solving with Union-Find?" type: choice options: ["connected components", "cycle detection", "Kruskal MST", "equivalence classes", "dynamic connectivity", "percolation"] - key: optimization question: "Which optimizations do you need?" type: choice options: ["path compression only", "union by rank only", "both (recommended)", "weighted union-find (track component metadata)"] # === DISTRIBUTION === canonical_source: "https://knowledgelib.io/software/patterns/union-find-disjoint-set/2026" suggested_citation: "Source: knowledgelib.io -- AI Knowledge Library (verified 2026-02-24)" # === RELATED UNITS === related_kos: related_to: - id: software/patterns/graph-algorithms/2026 label: "Graph Algorithms" - id: software/patterns/topological-sort/2026 label: "Topological Sort" - id: software/patterns/dynamic-programming/2026 label: "Dynamic Programming" solves: - id: software/patterns/kruskal-mst/2026 label: "Kruskal's Minimum Spanning Tree" - id: software/patterns/connected-components/2026 label: "Connected Components" alternative_to: - id: software/patterns/bfs-dfs-traversal/2026 label: "BFS/DFS Graph Traversal" often_confused_with: - id: software/patterns/adjacency-list-matrix/2026 label: "Adjacency List/Matrix Representations" # === SOURCES (7 authoritative sources) === sources: - id: src1 title: "Disjoint Set Union -- Algorithms for Competitive Programming" author: CP-Algorithms url: https://cp-algorithms.com/data_structures/disjoint_set_union.html type: community_resource published: 2024-06-15 reliability: authoritative - id: src2 title: "Introduction to Disjoint Set (Union-Find Data Structure)" author: GeeksforGeeks url: https://www.geeksforgeeks.org/dsa/introduction-to-disjoint-set-data-structure-or-union-find-algorithm/ type: community_resource published: 2025-01-10 reliability: high - id: src3 title: "Disjoint-set data structure" author: Wikipedia url: https://en.wikipedia.org/wiki/Disjoint-set_data_structure type: community_resource published: 2025-12-01 reliability: high - id: src4 title: "Union By Rank and Path Compression in Union-Find Algorithm" author: GeeksforGeeks url: https://www.geeksforgeeks.org/dsa/union-by-rank-and-path-compression-in-union-find-algorithm/ type: community_resource published: 2025-03-20 reliability: high - id: src5 title: "Kruskal's Minimum Spanning Tree Algorithm" author: GeeksforGeeks url: https://www.geeksforgeeks.org/dsa/kruskals-minimum-spanning-tree-algorithm-greedy-algo-2/ type: community_resource published: 2025-02-15 reliability: high - id: src6 title: "Disjoint Set Union (Union Find)" author: HackerEarth url: https://www.hackerearth.com/practice/notes/disjoint-set-union-union-find/ type: community_resource published: 2024-08-01 reliability: moderate_high - id: src7 title: "WeightedQuickUnionPathCompressionUF.java -- Algorithms, 4th Edition" author: Robert Sedgewick & Kevin Wayne url: https://algs4.cs.princeton.edu/15uf/WeightedQuickUnionPathCompressionUF.java.html type: academic_paper published: 2024-01-01 reliability: authoritative --- # Union-Find (Disjoint Set): Complete Reference ## TL;DR - **Bottom line**: Union-Find (Disjoint Set Union) maintains a partition of elements into disjoint sets, supporting near-O(1) amortized find and union operations when using both path compression and union by rank. - **Key tool/command**: `parent[]` array with `find(x)` (path compression) + `union(a, b)` (by rank/size) - **Watch out for**: Forgetting path compression -- without it, find degrades to O(n) on skewed trees. - **Works with**: Any language; no dependencies. Standard library support in Python (`scipy.cluster.hierarchy`), C++ (Boost), Java (no stdlib but trivial to implement). ## Constraints - Union-Find only works on equivalence relations (reflexive, symmetric, transitive) -- it cannot model directed edges or asymmetric relationships - Cannot efficiently undo union operations -- once two sets are merged, splitting requires a rollback variant or offline processing - Path compression mutates the tree during find, making the structure non-persistent -- use immutable/persistent DSU if you need historical snapshots - Union-Find does not support shortest-path, weighted-edge queries, or neighbor enumeration -- it only answers "are X and Y connected?" - Union by rank and union by size are mutually exclusive -- mixing them corrupts rank invariants ## Quick Reference | Operation | Naive (linked list) | Path Compression Only | Union by Rank Only | Both Optimizations | Amortized (Both) | |---|---|---|---|---|---| | `make_set(x)` | O(1) | O(1) | O(1) | O(1) | O(1) | | `find(x)` | O(n) | O(log n)* | O(log n) | O(alpha(n)) | ~O(1) | | `union(a, b)` | O(n) | O(log n)* | O(log n) | O(alpha(n)) | ~O(1) | | `connected(a, b)` | O(n) | O(log n)* | O(log n) | O(alpha(n)) | ~O(1) | | Space | O(n) | O(n) | O(n) | O(n) | O(n) | | Component count | O(1) with counter | O(1) with counter | O(1) with counter | O(1) with counter | O(1) | | Component size | O(n) | O(n) | O(1) with size[] | O(1) with size[] | O(1) | | Undo last union | Not supported | Not supported | Not supported | Not supported | Use rollback DSU | *Amortized over sequence of m operations: O(m * alpha(n)) total, where alpha is the inverse Ackermann function (effectively <= 4 for any practical n < 10^600). [src1] [src3] ## Decision Tree ``` START: Do you need to track connectivity between elements? | +-- YES: Are edges added online (one at a time)? | | | +-- YES: Do you need to undo/remove edges? | | | | | +-- YES --> Use Link-Cut Trees or Offline DSU with rollback | | +-- NO --> Union-Find (this unit) -- optimal choice | | | +-- NO (all edges known upfront): Do you need more than connectivity? | | | +-- YES (shortest path, all neighbors, etc.) --> BFS/DFS on adjacency list | +-- NO (just connected components) --> Union-Find OR BFS/DFS (both work) | +-- NO: Do you need to find minimum spanning tree? | +-- YES: Dense graph (E >> V)? | | | +-- YES --> Prim's algorithm with priority queue | +-- NO --> Kruskal's algorithm + Union-Find (this unit) | +-- NO --> This unit is not applicable ``` ## Step-by-Step Guide ### 1. Implement the basic data structure Initialize a parent array where each element is its own parent (self-loop = root). Optionally track rank and component count. [src1] ```python class UnionFind: def __init__(self, n): self.parent = list(range(n)) # Each element is its own root self.rank = [0] * n # Rank for union by rank self.count = n # Number of connected components ``` **Verify**: `uf = UnionFind(5)` -> `uf.parent == [0, 1, 2, 3, 4]`, `uf.count == 5` ### 2. Implement find with path compression Path compression flattens the tree by making every node on the find path point directly to the root. This is the single most important optimization. [src1] [src4] ```python def find(self, x): if self.parent[x] != x: self.parent[x] = self.find(self.parent[x]) # Path compression return self.parent[x] ``` **Verify**: After `find(x)`, every node on the path from x to root has root as direct parent. ### 3. Implement union by rank Always attach the shorter tree under the taller tree. This keeps the tree height logarithmic even without path compression. [src1] [src4] ```python def union(self, x, y): root_x = self.find(x) root_y = self.find(y) if root_x == root_y: return False # Already in the same set # Union by rank: attach smaller tree under larger if self.rank[root_x] < self.rank[root_y]: root_x, root_y = root_y, root_x self.parent[root_y] = root_x if self.rank[root_x] == self.rank[root_y]: self.rank[root_x] += 1 self.count -= 1 return True # Merge happened ``` **Verify**: `uf.union(0, 1)` -> `uf.count == 4`, `uf.find(0) == uf.find(1)` ### 4. Add connected query and component tracking ```python def connected(self, x, y): return self.find(x) == self.find(y) def component_count(self): return self.count ``` **Verify**: `uf.union(0, 1); uf.union(1, 2)` -> `uf.connected(0, 2) == True`, `uf.count == 3` ### 5. (Optional) Track component sizes with union by size Replace rank with size for applications that need component sizes (e.g., percolation, largest component). [src2] ```python class UnionFindBySize: def __init__(self, n): self.parent = list(range(n)) self.size = [1] * n self.count = n def find(self, x): if self.parent[x] != x: self.parent[x] = self.find(self.parent[x]) return self.parent[x] def union(self, x, y): root_x, root_y = self.find(x), self.find(y) if root_x == root_y: return False if self.size[root_x] < self.size[root_y]: root_x, root_y = root_y, root_x self.parent[root_y] = root_x self.size[root_x] += self.size[root_y] self.count -= 1 return True def get_size(self, x): return self.size[self.find(x)] ``` ## Code Examples ### Python: Kruskal's MST with Union-Find ```python # Input: n (vertices), edges as [(weight, u, v), ...] # Output: MST edges and total weight def kruskal_mst(n, edges): uf = UnionFind(n) edges.sort() # Sort by weight mst = [] total_weight = 0 for weight, u, v in edges: if uf.union(u, v): # Only add if no cycle mst.append((u, v, weight)) total_weight += weight if len(mst) == n - 1: # MST complete break return mst, total_weight # Example: 4 nodes, 5 edges edges = [(1, 0, 1), (2, 1, 2), (3, 0, 2), (4, 2, 3), (5, 1, 3)] mst, cost = kruskal_mst(4, edges) # mst = [(0,1,1), (1,2,2), (2,3,4)], cost = 7 ``` ### JavaScript: Union-Find with Path Compression and Rank > Full script: [javascript-union-find-with-path-compression-and-ra.js](scripts/javascript-union-find-with-path-compression-and-ra.js) (25 lines) ```javascript // Input: n (number of elements) // Output: UnionFind object with find, union, connected methods class UnionFind { constructor(n) { this.parent = Array.from({length: n}, (_, i) => i); # ... (see full script) ``` ### Java: Union-Find for Cycle Detection in Undirected Graph > Full script: [java-union-find-for-cycle-detection-in-undirected-.java](scripts/java-union-find-for-cycle-detection-in-undirected-.java) (27 lines) ```java // Input: n vertices, int[][] edges (each [u, v]) // Output: true if graph contains a cycle public class UnionFind { private int[] parent, rank; public UnionFind(int n) { # ... (see full script) ``` ### C++: Union-Find with Size Tracking ```cpp // Input: n (number of elements) // Output: DSU struct with find, unite, connected, get_size struct DSU { vector parent, sz; int components; DSU(int n) : parent(n), sz(n, 1), components(n) { iota(parent.begin(), parent.end(), 0); } int find(int x) { return parent[x] == x ? x : parent[x] = find(parent[x]); } bool unite(int a, int b) { a = find(a); b = find(b); if (a == b) return false; if (sz[a] < sz[b]) swap(a, b); parent[b] = a; sz[a] += sz[b]; components--; return true; } bool connected(int a, int b) { return find(a) == find(b); } int get_size(int a) { return sz[find(a)]; } }; ``` ## Anti-Patterns ### Wrong: Find without path compression ```python # BAD -- O(n) worst case per find, tree becomes a linked list def find(self, x): while self.parent[x] != x: x = self.parent[x] return x ``` ### Correct: Find with path compression ```python # GOOD -- amortized O(alpha(n)) per find, tree stays flat def find(self, x): if self.parent[x] != x: self.parent[x] = self.find(self.parent[x]) return self.parent[x] ``` ### Wrong: Union without rank/size (naive attachment) ```python # BAD -- always attaches y's root under x's root, can create O(n) chains def union(self, x, y): root_x, root_y = self.find(x), self.find(y) if root_x != root_y: self.parent[root_y] = root_x # No rank/size check ``` ### Correct: Union by rank ```python # GOOD -- keeps tree balanced, O(log n) height guarantee def union(self, x, y): root_x, root_y = self.find(x), self.find(y) if root_x == root_y: return False if self.rank[root_x] < self.rank[root_y]: root_x, root_y = root_y, root_x self.parent[root_y] = root_x if self.rank[root_x] == self.rank[root_y]: self.rank[root_x] += 1 return True ``` ### Wrong: Mixing rank and size in the same structure ```python # BAD -- updating rank as if it were size corrupts the invariant def union(self, x, y): root_x, root_y = self.find(x), self.find(y) if root_x != root_y: if self.rank[root_x] < self.rank[root_y]: root_x, root_y = root_y, root_x self.parent[root_y] = root_x self.rank[root_x] += self.rank[root_y] # Wrong! Rank != size ``` ### Correct: Either rank (increment only on tie) or size (always add) ```python # GOOD -- rank: only increment when ranks are equal if self.rank[root_x] == self.rank[root_y]: self.rank[root_x] += 1 # GOOD -- size: always add sizes together self.size[root_x] += self.size[root_y] ``` ## Common Pitfalls - **Forgetting to call find() before comparing roots**: Comparing `parent[x] == parent[y]` instead of `find(x) == find(y)` gives wrong results because parent may not be the root after path compression. Fix: always use `find()`. [src1] - **Stack overflow with recursive find on large inputs**: Recursive path compression can exceed stack depth for n > 10^5. Fix: use iterative path compression with two passes, or increase stack size. [src1] - **Not returning whether union actually merged**: Many algorithms (Kruskal, cycle detection) need to know if a union created a new connection. Fix: return `True/False` from `union()`. [src5] - **Using Union-Find for directed graph cycle detection**: Union-Find only detects cycles in undirected graphs. For directed graphs, use DFS with coloring (white/gray/black). Fix: check graph type before choosing algorithm. [src2] - **Initializing parent array to 0 instead of identity**: `parent = [0] * n` makes every element's root 0, which is wrong. Fix: `parent = list(range(n))` or `parent[i] = i` in a loop. [src6] - **Forgetting to decrement component count on union**: If you track component count, every successful union must decrement it. Fix: `if root_x != root_y: self.count -= 1`. [src7] ## When to Use / When Not to Use | Use When | Don't Use When | Use Instead | |---|---|---| | Checking if two nodes are in the same connected component | You need the actual path between two nodes | BFS/DFS traversal | | Building MST with Kruskal's algorithm | Graph is dense (E close to V^2) | Prim's algorithm with adjacency matrix | | Detecting cycles in undirected graphs | Detecting cycles in directed graphs | DFS with back-edge detection | | Grouping equivalent items (e.g., accounts merge, synonyms) | You need to split groups or undo unions | Link-Cut Trees or offline rollback DSU | | Online connectivity (edges added one at a time) | All edges known upfront and you need full traversal | BFS/DFS is simpler | | Percolation simulation / grid connectivity | You need weighted shortest path | Dijkstra or Bellman-Ford | | Very large graphs (10^6+ nodes) where BFS/DFS is too slow | Graph fits in memory and BFS/DFS is fast enough | BFS/DFS (simpler to code) | ## Important Caveats - The inverse Ackermann function alpha(n) is effectively constant (<= 4) for any practical input size, but this is an amortized bound -- individual operations can still take O(log n) in the worst case. [src3] - Path compression is not thread-safe by default. For concurrent applications, use atomic compare-and-swap or lock the find/union operations. [src1] - Union-Find with path compression is not suitable for persistent/functional data structures -- each find mutates the tree. For immutable settings, use weighted union without path compression (O(log n) per op). [src3] - Python's default recursion limit (1000) will cause `RecursionError` for large inputs with recursive path compression. Use `sys.setrecursionlimit()` or switch to iterative find. [src2] - In competitive programming, iterative path compression (using a while loop + second pass) is preferred over recursive to avoid stack overflow on judge systems. ## Related Units - [Graph Algorithms](/software/patterns/graph-algorithms/2026) - [Topological Sort](/software/patterns/topological-sort/2026) - [Dynamic Programming](/software/patterns/dynamic-programming/2026)