UnionFind

A different view on the dynamic connectivity problem through the lens of Quick-Find.

Context

Union-Find (also called Disjoint Set Union, DSU) is a data structure for solving the dynamic connectivity problem.

Given a set of elements, it supports two operations:

• union / connect(p, q) — connect two elements
• find(p) — determine which component an element belongs to

Two elements are connected if they belong to the same component.

This article presents the naive Quick-Find implementation — not because it’s fast, but because it makes the problem and its tradeoffs explicit.

Core idea

• Maintain an array where data[i] represents the component id of element i
• Initially, each element is its own component
• Two elements are connected if their component ids match

Tradeoff:

• find / isConnected → O(1)
• union → O(n) (requires scanning the entire array)

This asymmetry is intentional and motivates better variants.

Implementation

Quick-Find

import java.util.Arrays;

public class UnionFind {
    private int count;
    private final int[] data;
    
    public UnionFind(int size) {
        data = new int[size];
        
        for (var i = 0; i < size; i++) {
            data[i] = i;
        }
    
        count = size;
    }
    
    public void connect(int p, int q) {
        var componentP = data[p];
        var componentQ = data[q];
        
       if (componentP == componentQ) return;
       
       for (var i = 0; i < data.length; i++) {
            if (data[i] == componentP) data[i] = componentQ;
       } 
       
       count--;
    }
    
    public boolean isConnected(int p, int q) {
        return data[p] == data[q];
    }
    
    public int find(int p) { return data[p]; }
    
    public int size() { return count; }
    
    @Override
    public String toString() { return Arrays.toString(data); }
}