Union Find

Union Find is a data structure to

  1. find whether two elements in the same group (Find)
  2. merge two groups of elements (Union)

Here is an example story to help you understand Union Find.
A, B, C three people work for M company. We assign them each a parent pointer to M.
D, E, F, G four people work for L company. We assign them each a parent pointer to L.

Parent pointer tells which group a person belongs to. A’s parent is M. F’s parent is L. Suppose A meets F, they know they are not in the same company. If D comes, F knows D is a colleague.

Suppose one day M acquired L. We simply let M be L’s parent. Then D, E, F, G all join M.

Union Find Basic Operations

1. Initialization

We can simply initialize Union Find by assigning each element’s parent to themselves.

2. Find

To find which group the element belongs to.

Time Complexity: O(1).

3. Union

Merge two groups into one group.

Time Complexity: O(1).

One thought

Leave a Reply

Your email address will not be published. Required fields are marked *