Disjoint Sets (Union-Find Data Structure)

The Disjoint Set (also called the Union-Find data structure) is a collection of non-overlapping (disjoint) dynamic sets. It efficiently supports operations that determine whether two elements belong to the same set and combine two sets into one.

This data structure is widely used in:

Kruskal's Minimum Spanning Tree (MST) – Detects whether adding an edge creates a cycle.

Connected Components – Maintains dynamic connectivity in an undirected graph.

Network Connectivity – Determines whether two computers or nodes are connected.

Image Processing – Labels connected regions in binary images.

Clustering Algorithms – Merges related groups of data efficiently.

Equivalence Relations – Represents partitions of elements into equivalence classes.

1. Definition

A disjoint-set data structure maintains a collection

$$S=\{S_1,S_2,\ldots,S_k\}$$

such that

• Every element belongs to exactly one set.
• No two sets overlap.

Example

Universe U = {1,2,3,4,5,6,7,8}

Sets

S1 = {1,2}
S2 = {3,4,5}
S3 = {6}
S4 = {7,8}

No element appears in more than one set.

---

2. Basic Operations

CLRS defines three fundamental operations.

(a) MAKE-SET(x)

Creates a new set containing only element x.

Initially,

MAKE-SET(1)
MAKE-SET(2)
MAKE-SET(3)

Results

{1}
{2}
{3}

Each element starts as its own representative.

---

(b) UNION(x,y)

Combines the sets containing x and y.

Suppose

{1}
{2}
{3}

Perform

UNION(1,2)

Result

{1,2}
{3}

---

(c) FIND-SET(x)

Returns the representative of the set containing x.

Example

Set

{1,2,3}

Representative = 1

FIND-SET(2)

returns

1

The representative can be any one element of the set, but it uniquely identifies the set.

---

3. Why Representatives?

Instead of comparing entire sets,

Are 3 and 7 in the same set?

we simply compare

FIND-SET(3)

FIND-SET(7)

If representatives are equal,

they belong to the same set.

Otherwise,

they belong to different sets.

---

4. Sequence of Operations

Initially

MAKE-SET(A)
MAKE-SET(B)
MAKE-SET(C)
MAKE-SET(D)

Sets

{A}
{B}
{C}
{D}

Now

UNION(A,B)

{A,B}
{C}
{D}

Then

UNION(C,D)

{A,B}
{C,D}

Finally

UNION(A,C)

Result

{A,B,C,D}