Union Find is a data structure to

- find whether two elements in the same group (Find)
- 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.

1 2 3 4 5 6 7 8 |
int[] parent; public UnionFind(int n) { parent = new int[n]; for (int i = 0; i < n; i++) { parent[i] = i; } } |

### 2. Find

To find which group the element belongs to.

1 2 3 4 5 6 |
private int find(int x) { if (parent[x] == x) { return x; } return parent[x] = find(parent[x]); } |

Time Complexity: O(1).

### 3. Union

Merge two groups into one group.

1 2 3 4 5 6 7 |
public void union(int a, int b) { int rootA = find(a); int rootB = find(b); if (rootA != rootB) { parent[rootA] = rootB; } } |

Time Complexity: O(1).

Thanks for the article and explanation.