**Post: #1**

Disjoint Sets

Disjoint Sets.ppt (Size: 302.5 KB / Downloads: 65)

Equivalence Relations

A relation R is defined on a set S if for every pair of elements (a,b), a,bS, a R b is either true or false. If a R b is true, then we say that a is related to b.

An equivalence relation is a relation R that satisfy three properties:

(reflexive) a R a, for all a S.

(symmetric) a R b if and only if b R a.

(transitive) a R b and b R c implies that a R c.

Disjoint Sets

Make the input a collection of N sets, each with one element.

All relations (except reflexive) are false;

Each set has a different element: SiSj= => it makes the sets disjoint.

Find operation: returns the name of the set containing a given element.

Add/Union operation (e.g., add relation a~b)

Check if a and b are already related: if they are in the same equivalence class.

If not, apply “union”: merge the two equivalence classes containing a and b into a new equivalence class.

Example:

On a set of subsets, the three operations amount to:

Create a set of n disjoint subsets with every node in its own subset

Test whether A and B are in the same subset

If A and B are in the same subset, then do nothing, else unify the subsets to which A and B belong

Union and Find

The Union-Find problem starts with n elements (numbered 1 to n), each one representing a singleton set. We allow two operations to be performed: