Union Find

Union Find data structure is also known as disjoint set data structure. It is a data structure which stores a collection of disjoint sets. It provides two operations, one for merging two sets and one for finding the set with a given element.

Union Find

There is an array called parents in the Union Find data structure. It records the set to which each element belongs. Initially, each element forms a set by itself. Afterwards, the given two sets are merged by calling union(). find() returns the set number of the passed element.

public class UnionFind {
    private final int[] parents;

    public UnionFind(int size) {
        parents = new int[size];
        for (int i = 0; i < size; i++) {
            parents[i] = i;
        }
    }

    int find(int x) {
        while (x != parents[x]) {
            parents[x] = parents[parents[x]];
            x = parents[x];
        }
        return x;
    }

    void union(int x, int y) {
        int parentX = find(x);
        int parentY = find(y);

        if (parentX < parentY) {
            parents[parentY] = parentX;
        } else if (parentX > parentY) {
            parents[parentX] = parentY;
        }
    }
}

Time and Space Complexity

When initializing parents, the required time complexity is O(n), where n is the number of elements.

The time complexity required by Find() is O(α(n)), where α is the inverse Ackermann function , it grows very slowly, so it can be regarded as constant time. So, O(α(n)) ≈ O(1). Therefore, the time complexity of Find() is O(1).

Union() uses Find(), so its time complexity is O(1).

The Union Find data structure requires a parents internally. So, its space complexity is O(n).

Example

Reference

• Ellis Horowitz, Sartaj Sahni, Sanguthevar Rajasekaran, Computer Algorithm.
• Disjoint-set data structure, Wikipedia.