# 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)

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.

```    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.

```    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.

```    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).

## One Thought to “Union Find”

1. jatin waghela says:

Thanks for the article and explanation.