The disjoint sets data structure stores

elements in sets. Every element is in one

set, which is why the sets are disjoint. For

example, in the following figure, we store

the elements $1,2,3,4,5,6$ in three disjoint

sets.

The disjoint sets data structure supports

three operations:

$$ Create$($x$)$ creates a new set that contains the single new element x$.$

$$ Find$($x$)$ return the name of the set that contains

the element x$.$

$$ Union$($Y$,$Z$)$ merge the two sets y and Z into one

larger set.

For example, the current figure shows the situation after

running Union$($A$,$C$)$ in the above figure.

We will soon see in class that this is a useful data

structure.