A binary relation R is an equivalence relation if it is reflexive, symmetric, and transitive. Any equivalence relation R defined on a set S of elements partitions S into a collection { S1, , Sk } of disjoint sets where each Si has all and only the elements x, y such that R(x, y) holds.

Design a high-level algorithm to compute the disjoint sets with respect to an equivalence relation R defined on a set S. In your algorithm you are allowed to use only the following four operations: Make-Set(x), Union(x, y), Find-Set(x), and R(x, y) which is a Boolean operation to decide if R(x, y) holds. Of course you may use conditionals and loops, including loops over the elements of S and over the pairs of elements of S. Analyze the # of times each of the four operations is performed in your algorithm.

Trace the execution of your algorithm on the example below:

S = { a, b, c, d, e }. R(a, c), R(c, a), R(b, d), R(d, b) hold, and these are the only non-reflexive instances of R.