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.

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