Disjoint Set (Union-Find) Data Structure Visualizer

How to Use

Initialize: Set size (e.g., 8) and click "Initialize"
Sample Data: Click Sample Data to see example unions.
Union: Enter two elements (e.g., X=1, Y=3) and click "Union"
Find: Enter element to find its root representative
Connected: Check if two elements are in the same set

Disjoint Set Concept

Disjoint Set (Union-Find) maintains a collection of disjoint (non-overlapping) sets.

Key Operations:

Find: Determine which set an element belongs to
Union: Merge two sets into one
Connected: Check if two elements are in the same set

Optimizations:

Path Compression: Make trees flatter during Find
Union by Rank: Attach smaller tree under larger tree
Nearly O(1): Amortized time complexity with optimizations

How it Works: Each element initially forms its own set. Union operations merge sets by making one root point to another. Find operations trace parent pointers to reach the root.

Use Cases

Kruskal's minimum spanning tree algorithm
Network connectivity problems
Image processing (connected components)
Social network analysis (friend groups)
Percolation theory and physics simulations

Time Complexity

Operation	Naive	Optimized
Find	O(n)	O(Î±(n))
Union	O(n)	O(Î±(n))
Connected	O(n)	O(Î±(n))

Î±(n) = inverse Ackermann function (practically constant)

Space Complexity

Component	Space
Parent Array	O(n)
Rank Array	O(n)

Advantages

Nearly constant time operations
Simple implementation
Memory efficient
Excellent for connectivity queries

Optimizations

Path Compression: During Find, make all nodes point directly to root

Union by Rank: Always attach tree with smaller rank to tree with larger rank

Combined: Both optimizations together give Î±(n) amortized time

Disjoint Set (Union-Find) Data Structure Visualizer

Disjoint Set Setup

Parent Array

Union-Find Operations

Statistics

Disjoint Set Visualization

Operation Steps