QuickUnion

A near-constant time solution to dynamic connectivity using weighted trees and path compression.

Context

QuickUnion is a significantly improved version of Quick-Find, addressing its inefficiencies by representing components as trees rather than flat labels.

Two optimizations make it fast in practice:

• Weighting ensures that smaller trees are always attached under larger ones, preventing tall, degenerate structures.
• Path compression flattens the tree during find operations by making each visited node point closer to the root. If a node’s parent is not a root, there is no reason not to rewire it to its grandparent.

Combined, these techniques dramatically reduce tree height and make connectivity operations almost constant time in practice.

Core idea

• Maintain two arrays:
  • data[] — parent links forming a forest of trees
  • sizes[] — the size (or weight) of each tree, stored at the root
• Each connected component is represented by a tree whose root is its representative.
• Two elements are connected if they have the same root.
• When connecting two components:
  • Find both roots
  • Attach the smaller tree under the larger one using sizes
• During root lookup, apply path compression to reduce future lookup costs.

Implementation

import java.util.Arrays;

public class QuickUnion {
    private final int[] data;
    private final int[] sizes;
    private int count;
    
    public QuickUnion(int n) {
        data = new int[n];
        sizes = new int[n];
        for (var i = 0; i < n; i++) {
            data[i] = i;
            sizes[i] = 1;
        }
        count = n;   
    }
    
    public int size() { return count; }
    
    public boolean isConnected(int p, int q) {
        return root(p) == root(q);
    }
    
    public int find(int p) { return root(p); }
    
    public void connect(int p, int q) {
        var cmpP = root(p);
        var cmpQ = root(q);
        
        if (cmpP == cmpQ) return;
        
        if (sizes[cmpP] < sizes[cmpQ]) {
            data[cmpP] = cmpQ;
            sizes[cmpQ] += sizes[cmpP];
        } else {
            data[cmpQ] = cmpP;
            sizes[cmpP] += sizes[cmpQ];
        }
        
        count--;
    }
    
    private int root(int p) {
        while (p != data[p]) {
            data[p] = data[data[p]];
            p = data[p];
        }
        return p;
    }
    
    @Override
    public String toString() { return Arrays.toString(data); }
}