Union - Find Algorithms

[1] Basic Abstractions:

• Set of Objects

• Union Command – connect two objects.

• Find Query – if there is a path that would connect one input to another.

[2] A Union-Find data structure maintains a partition of a set X of size n. For each set A in the partition it maintains a representative S(A) contained in A. The initial partition has each element in a set by itself.Operations include:

[2] Union(S(A), S(B)), where S(A) ≠ S(B), replaces A and B by A U B, and specifies a representative for A U B.

[2] Find(x), where x ∈ X, returns S(Ax), the representative of the set containing x.

Reference:
[1] http://www.cs.princeton.edu/~rs/AlgsDS07/01UnionFind.pdf
[2] http://www.cs.berkeley.edu/~karp/greatalgo/lecture08.pdf