Java union-find: connected components and path compression

Java 8+. The program uses only JDK classes and runs without a framework.

Connectivity is less information than a route

A depot network receives links between locations and must answer whether two locations belong to the same connected group. Union-find can answer that after processing the links. It cannot return a route, a shortest distance or the edges that connect the locations; those require a graph representation.

The implementation stores one parent per depot and one size per component root. Merging attaches the smaller root’s tree under the larger one. During find, path compression shortens a visited chain so future lookups perform less repeated work.

The parent array is an implementation tree over component membership, not the physical road network. After compression, a parent link may join two depot IDs that have no direct road between them. Treating that link as a travel step would invent an edge.

Deletion changes the problem

Merging links only combines groups. Removing one physical road may split a group, and this basic structure cannot undo that split correctly. Rebuild connectivity from the remaining links, or use an algorithm designed for the required update pattern.

Every depot ID must be within the allocated domain. The program validates IDs in find, so both connected and connect calls inherit the boundary check. A repeated connect within one group returns false and leaves the component count unchanged. Compare BFS when an actual traversal or path is required.

Working program

public class DepotComponents {
    private final int[] parent;
    private final int[] size;
    private int groups;
    DepotComponents(int depots) {
        if (depots < 0) throw new IllegalArgumentException("Negative depot count");
        parent = new int[depots];
        size = new int[depots];
        groups = depots;
        for (int depot = 0; depot < depots; depot++) {
            parent[depot] = depot;
            size[depot] = 1;
        }
    }
    int find(int depot) {
        if (depot < 0 || depot >= parent.length) throw new IllegalArgumentException("Unknown depot");
        while (depot != parent[depot]) {
            parent[depot] = parent[parent[depot]];
            depot = parent[depot];
        }
        return depot;
    }
    boolean connect(int first, int second) {
        int firstRoot = find(first), secondRoot = find(second);
        if (firstRoot == secondRoot) return false;
        if (size[firstRoot] < size[secondRoot]) {
            int swap = firstRoot; firstRoot = secondRoot; secondRoot = swap;
        }
        parent[secondRoot] = firstRoot;
        size[firstRoot] += size[secondRoot];
        groups--;
        return true;
    }
    public static void main(String[] args) {
        DepotComponents network = new DepotComponents(5);
        network.connect(0, 1);
        network.connect(1, 2);
        System.out.println(network.find(0) == network.find(2));
        System.out.println(network.find(0) == network.find(4));
        System.out.println("groups=" + network.groups);
        System.out.println("merged=" + network.connect(0, 2));
    }
}

Output

true
false
groups=3
merged=false

Cost and failure boundaries

The arrays require O(v) storage and initialization for v depots. Union by size with path compression gives near-constant amortized cost, commonly expressed using the inverse Ackermann function. That is a bound across an operation sequence, not a promise that every find performs one array access.

Compression writes parent entries, so this implementation is not safe for concurrent callers without a coordination rule. Tests should cover isolated IDs, transitive links, repeated merges, invalid IDs and two initially separate groups joined by one later link. A component count is useful for checking that redundant links do not reduce the total.

Common Mistakes

• Do not read parent links as roads or shortest paths.
• Do not expect basic union-find to split a component after edge deletion.
• Do not decrement the component count for an already connected pair.

Connect the contracts

Compare the boundary explained in Graph reachability with the assumptions made by this program.

Compare the boundary explained in Indexed storage with the assumptions made by this program.