Quick Find for Union-Find

This section builds upon the structure of the Union-Find data structure introduced in the previous section to describe basic operations: find, union, and checking connectivity.

To find the set number of an element, simply return the value from the id array, which has a time complexity of O(1).

...
private int find(int p) {
    assert p >= 0 && p < count;
    return id[p];
}
...

To merge the sets of elements p and q, the process involves iterating through all elements and then merging the set numbers of the two elements, which has a time complexity of O(n).

...
public void unionElements(int p, int q) {
    int pID = find(p);
    int qID = find(q);
    if (pID == qID)
        return;
    for (int i = 0; i < count; i++)
        if (id[i] == pID)
            id[i] = qID;
}
...

Java Example Code

Source Code Download: Download

UnionFind1.java File Code:

package tutorialpro.union;

/**
 * First version of union-Find
 */
public class UnionFind1 {
    // Our first version of Union-Find is essentially an array
    private int[] id;
    // Number of elements
    private int count;

    public UnionFind1(int n) {
        count = n;
        id = new int[n];
        // Initialization, each id[i] points to itself, no merged elements
        for (int i = 0; i < n; i++)
            id[i] = i;
    }

    // Find process, find the set number of element p
    private int find(int p) {
        assert p >= 0 && p < count;
        return id[p];
    }

    // Check if elements p and q belong to the same set
    // O(1) complexity
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }

    // Merge the sets of elements p and q
    // O(n) complexity
    public void unionElements(int p, int q) {

        int pID = find(p);
        int qID = find(q);

        if (pID == qID)
            return;

        // The merge process requires iterating through all elements, merging the set numbers of the two elements
        for (int i = 0; i < count; i++)
            if (id[i] == pID)
                id[i] = qID;
    }
}