Find:

Union:+

Presets:

Overview & Concept

Disjoint Set Union (DSU), also known as Union-Find, is a data structure that tracks a set of elements partitioned into a number of disjoint (non-overlapping) subsets. It provides near-constant time operations to determine which subset an element belongs to (find) and join two subsets into a single subset (union). Combining Path Compression with Union by Rank achieves an amortized time complexity of O(alpha(n)) per operation, where alpha is the inverse Ackermann function (effectively alpha(n) < 5 for all practical universe sizes).

How It Works

Forest Representation: Subsets are represented as trees of directed parent pointers. The root node represents the canonical set identifier.

Root Representative: A node is a set root if and only if parent[x] == x.

Path Compression: During find(x), the algorithm traverses up to the root, then flattens the tree by rewiring all visited nodes directly to the root.

Union by Rank: When merging two sets, the root with smaller rank is attached as a child of the root with larger rank, keeping tree depth minimal.

Step-by-Step Execution

1. makeSet(n)Initialize n singleton elements with parent[i] = i and rank[i] = 0.

2. find(x) with Path CompressionClimb parent pointers to locate root representative, then rewire all traversed nodes directly to root.

3. Root ComparisonIn union(x, y): compute rootX = find(x) and rootY = find(y). If rootX == rootY, abort (already in same set).

4. Union by Rank AttachmentAttach smaller rank root under larger rank root. If ranks are tied, attach rootY under rootX and increment rank[rootX].

Asymptotic Complexity Analysis

Metric	Best Case	Average Case	Worst Case	Space Complexity
Complexity Bound	O(1) amortized	O(alpha(n)) near constant	O(alpha(n)) where alpha is inverse Ackermann function	O(n)
Explanation	Optimal input arrangement minimizing operations.	Expected time for uniformly distributed randomized inputs.	Adversarial degenerate conditions requiring full traversal.	Auxiliary memory allocated beyond original input size.

Pseudocode & Invariants

Algorithm Logic

// Disjoint Set Union (DSU / Union-Find)
// Path Compression & Union by Rank

operation find(x):
  if parent[x] != x:
    parent[x] = find(parent[x]) // Path Compression
  return parent[x]

operation union(x, y):
  rootX = find(x); rootY = find(y)
  if rootX == rootY: return // Already united

  // Union by Rank
  if rank[rootX] < rank[rootY]: parent[rootX] = rootY
  else if rank[rootX] > rank[rootY]: parent[rootY] = rootX
  else:
    parent[rootY] = rootX
    rank[rootX] += 1

Algorithmic Invariants

Partition Invariant: Every element belongs to exactly one subset; subsets are pairwise disjoint.
Root Invariant: Exactly one canonical representative exists per connected component satisfying parent[root] == root.

Correctness Guarantee: Invariants hold true prior to loop entry, are preserved during every iteration, and guarantee correct post-condition upon termination.

Advantages & Disadvantages

Key Advantages

•Amortized near-constant time O(alpha(n)) per operation (effectively O(1)).
•Minimal memory overhead: requires only two 1D integer arrays (parent and rank).
•Core foundation of Kruskal's Minimum Spanning Tree and dynamic connectivity.

Trade-offs & Limitations

•Cannot split previously merged sets (monotonically non-decreasing connectivity).
•Restricted to undirected equivalence relations.

Real-World Applications

Kruskal's Minimum Spanning Tree

Cycle detection while iteratively adding minimal-weight edges in graph theory.

Network Connectivity & Percolation

Tracking dynamic physical cluster connections in materials science and social graphs.

Image Segmentation

Connected component labeling grouping contiguous pixels of similar color into segments.

Decision Guide: When to Use

Ideal Scenarios

✓When determining whether two elements belong to the same component.
✓When iteratively merging clusters or detecting cycles in undirected graphs.

Consider Alternatives When

✕When directed edge reachability is required (use BFS, DFS, or Tarjan).
✕When operations require separating or splitting existing sets.

Compare trade-offs and complexity across complementary tools in AlgoViz.

Breadth-First Search Depth-First Search Graph Workbench