What are Disjoint Sets?

Disjoint Sets are a data structure that maintains a collection of disjoint (non-overlapping) sets. The main operations supported by Disjoint Sets are:

1. MakeSet(x): Creates a new set containing the element ‘x’ and makes ‘x’ the representative (or parent) of this set.

2. Find(x): Returns the representative element of the set that contains ‘x’. The representative element is essentially an identifier for the entire set.

3. Union(x, y): Merges the sets that contain elements ‘x’ and ‘y’ into a single set. This is achieved by making the representative of one set point to the representative of the other set.

The Disjoint Sets data structure is useful in various algorithms and applications, such as finding connected components in a graph, cycle detection in a graph, and implementing efficient algorithms like Kruskal’s minimum spanning tree algorithm.

Equivalence Relations and Equivalence Classes

A relation between elements is known as an equivalence relation if it divides a set of elements into subsets, each of which contains components that are regarded as equivalent to one another under the particular relation.

To be an equivalence relation, the following three properties must hold for elements ‘a’, ‘b’, and ‘c’ in the set:

1. Reflexivity: For all ‘a’ in the set, ‘a’ is related to itself. (a ~ a)

2. Symmetry: If ‘a’ is related to ‘b’, then ‘b’ is related to ‘a’. (if a ~ b, then b ~ a)

3. Transitivity: If ‘a’ is related to ‘b’, and ‘b’ is related to ‘c’, then ‘a’ is related to ‘c’. (if a ~ b and b ~ c, then a ~ c)

For example, the relation "is equal to" is an equivalence relation because it satisfies these properties.

The subsets formed by an equivalence relation are called equivalence classes. Each equivalence class contains elements that are equivalent under the given relation. The original set is formed by union of all equivalence classes.