Quick Union of Disjoint Sets

For a set of data, the disjoint set mainly supports two operations:

• union(p, q) - Connects the elements p and q.
• find(p) - Finds which set the element p belongs to.
• isConnected(p, q) - Checks if the elements p and q are connected.

In the previous section, we represented the disjoint set using an id array, where the time complexity for finding was O(1), but the union operation was not efficient.

In this section, we will implement the disjoint set in another way. Each element is considered a node that points to its parent node, with the root node pointing to itself. As shown in the diagram, node 3 points to node 2, indicating that 3 and 2 are connected, and node 2, being the root, points to itself.

Similarly, we represent the disjoint set with an array, but this time using parent to indicate the parent node each element points to, with each element initially pointing to itself, making them independent.

If we perform union(4, 3), we make element 4 point to element 3:

The array is updated accordingly:

To determine if two elements are connected, we only need to check if they have the same root node.

In the diagram, nodes 4 and 9 both have root node 8, so they are connected.

To connect two elements, we find their respective root nodes and connect those roots, making the elements connected.

If we want to connect 6 and 4 in the diagram, we simply make the root of 6, which is 5, point to the root of 4, which is 8.

We construct this tree structure pointing to parent nodes using an array where parent[i] represents the parent node i points to.

...
private int[] parent;
private int count;  // Number of elements
...

The find process, which finds the set number of element p, continuously queries its parent node until it reaches the root node, characterized by parent[p] == p. This operation has a complexity of O(h), where h is the height of the tree.

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

To merge the sets of elements p and q, we find their root nodes and make one root point to the other, thus merging the two sets. This operation is also O(h), where h is the height of the tree.

public void unionElements(int p, int q){
    int pRoot = find(p);
    int qRoot = find(q);
    if( pRoot == qRoot )
        return;
    parent[pRoot] = qRoot;
}

Java Example Code

Source Code Download: Download

UnionFind2.java File Code:

package tutorialpro.union;
/**
 * Second version of unionFind
 */
public class UnionFind2 {
    // Our second version of Union-Find, using an array to build a tree pointing to parent nodes
    // parent[i] indicates the parent node of the first element
    private int[] parent;
    private int count;  // Number of elements
    // Constructor
    public UnionFind2(int count){
        parent = new int[count];
        this.count = count;
        // Initialization, each parent[i] points to itself, indicating each element forms its own set
        for( int i = 0 ; i < count ; i ++ )
            parent[i] = i;
    }
    // Find process, find the set number of element p
    // O(h) complexity, h is the height of the tree
    private int find(int p){
        assert( p >= 0 && p < count );
        // Continuously query the parent node until reaching the root node
        // Root node characteristic: parent[p] == p
        while( p != parent[p] )
            p = parent[p];
        return p;
    }
    // Check if elements p and q belong to the same set

// O(h) complexity, h is the height of the tree
public boolean isConnected(int p, int q) {
    return find(p) == find(q);
}
// Merge the sets to which elements p and q belong
// O(h) complexity, h is the height of the tree
public void unionElements(int p, int q) {
    int pRoot = find(p);
    int qRoot = find(q);
    if (pRoot == qRoot)
        return;
    parent[pRoot] = qRoot;
}