## Idea

Basically, the class contains two arrays, `parents`

and `ranks`

.

`parents`

stores the parent ID of a given ID.`ranks`

stores the rank of roots.

It supports two operations, `find`

and `union`

- For
`find(n1)`

, it will trace back from given ID to its parent, and parent’s parent, until reaching an element without a parent, i.e. a root.- an optimization here is attaching every elements on this tracing path to the final root, so that the height of the tree is reduced dramatically

- For
`union(n1, n2)`

, first we find the roots of two elements. If two roots are the same, do nothing (but it can be a useful tool to check whether an edge between two nodes makes cycle in a graph). Else, based on the ranks of two roots, we attach one to another to make the tree as balanced as possible.

## Analysis

### Union

Union operation takes time.

### Find

If we don’t do path shortening, the height of the tree is no more than , is the number of elements in the tree. Because the tree is balanced and a non-leaf node can have no less than 2 children. The time for a find operation is .

If we do the path shortening, there is a tricky proof says the time complexity for a sequence of operations is . There is a even more tricky one to lower this upper bound. I may post the proof later.

## Implementation

```
package unionFind;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
public class UnionFind {
private int[] parents;
private int[] ranks;
public UnionFind(int size) {
parents = new int[size];
Arrays.fill(parents, -1);
ranks = new int[size];
}
public int find(int curId) {
Queue<Integer> queue = new LinkedList<>();
while (parents[curId] != -1) {
queue.offer(curId);
curId = parents[curId];
}
while (!queue.isEmpty()) {
parents[queue.poll()] = curId;
}
return curId;
}
public void union(int root1, int root2) {
root1 = find(root1);
root2 = find(root2);
if (root1 == root2) {
return;
}
if (ranks[root1] < ranks[root2]) {
parents[root1] = root2;
} else if (ranks[root2] < ranks[root1]) {
parents[root2] = root1;
} else {
ranks[root1]++;
parents[root2] = root1;
}
}
}
```