Union-Find (Disjoint Set Union) — Dynamic Connectivity

Union-Find is a specialized data structure built for one specific question: are these two nodes in the same connected component? It answers this question in nearly O(1) amortized time, even as edges are added dynamically. BFS or DFS could also answer this question, but they’d cost O(V + E) per query. Union-Find answers thousands of queries at near-constant cost per query.

The difference is the use case: BFS/DFS is for when you need to traverse a static graph. Union-Find is for when you’re building a graph incrementally (adding edges one at a time) and need to track connectivity after each addition.

What Union-Find Solves

Dynamic connectivity: given a set of vertices and a sequence of edge additions, answer after each addition: “are vertices u and v in the same connected component?”

Applications where this pattern appears:

  • Kruskal’s MST: add edges in sorted order, skip if they’d create a cycle (meaning both endpoints already connected)

  • Number of Islands: union adjacent land cells, count distinct components

  • Accounts Merge: union accounts sharing an email address

  • Redundant Connection: find the edge that creates a cycle

Naive Implementation

Represent each element’s group with a parent[] array. Initially, every element is its own parent (its own group). Two operations:

  • find(x): return the root representative of x’s group

  • union(x, y): merge the groups of x and y

int[] parent;

void init(int n) {
    parent = new int[n];
    for (int i = 0; i < n; i++) parent[i] = i;  // each node is its own parent
}

int find(int x) {
    if (parent[x] != x) return find(parent[x]);  // recurse up to root
    return x;
}

void union(int x, int y) {
    int rx = find(x), ry = find(y);
    if (rx != ry) parent[rx] = ry;               // merge: make one root point to the other
}

boolean connected(int x, int y) {
    return find(x) == find(y);
}

Problem: if unions always attach one tree to another’s root, the tree can become a chain (like inserting sorted elements into a BST). find() degrades to O(n) in the worst case.

Optimization 1: Union by Rank

Always attach the smaller tree to the root of the larger tree. This keeps trees shallow — height is bounded by O(log n).

int[] parent, rank;

void init(int n) {
    parent = new int[n];
    rank   = new int[n];
    for (int i = 0; i < n; i++) { parent[i] = i; rank[i] = 0; }
}

void union(int x, int y) {
    int rx = find(x), ry = find(y);
    if (rx == ry) return;

    // Attach smaller-rank tree under larger-rank root
    if (rank[rx] < rank[ry]) parent[rx] = ry;
    else if (rank[rx] > rank[ry]) parent[ry] = rx;
    else { parent[ry] = rx; rank[rx]++; }    // equal rank: pick one, increment rank
}

With union by rank alone: find() is O(log n).

Optimization 2: Path Compression

During find(), make every node on the path point directly to the root. This flattens the tree incrementally — future find() calls on the same nodes become O(1).

int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]);  // path compression: point directly to root
    }
    return parent[x];
}

With path compression alone: find() is amortized O(log n).

Both Together: Near-Constant Time

Combining union by rank and path compression gives amortized O(α(n)) per operation, where α is the inverse Ackermann function — a function that grows so slowly it’s effectively constant for all practical input sizes (≤ 4 for n ≤ 10^80).

You don’t need to prove this. Name it if an interviewer asks about complexity, and move on.

Complete Implementation

class UnionFind {
    private int[] parent, rank;
    private int components;

    UnionFind(int n) {
        parent = new int[n];
        rank   = new int[n];
        components = n;
        for (int i = 0; i < n; i++) parent[i] = i;
    }

    int find(int x) {
        if (parent[x] != x)
            parent[x] = find(parent[x]);  // path compression
        return parent[x];
    }

    boolean union(int x, int y) {
        int rx = find(x), ry = find(y);
        if (rx == ry) return false;   // already connected — no merge needed

        if (rank[rx] < rank[ry])      parent[rx] = ry;
        else if (rank[rx] > rank[ry]) parent[ry] = rx;
        else { parent[ry] = rx; rank[rx]++; }

        components--;
        return true;   // merged: a new connection was established
    }

    boolean connected(int x, int y) {
        return find(x) == find(y);
    }

    int componentCount() { return components; }
}

The union() returning a boolean (was a new connection established?) is useful for Kruskal’s: if union() returns false, the edge would create a cycle and should be skipped.

What most people get wrong: implementing path compression or union by rank in isolation and thinking they’ve got the full optimization. Both are needed together for the O(α(n)) bound. Path compression alone is O(log n) amortized. Union by rank alone is O(log n). Together they achieve near-constant. Always implement both.

Application 1: Kruskal’s MST

Sort all edges by weight. For each edge in sorted order: if the two endpoints are not yet connected, add the edge to the MST and union them. Stop when V-1 edges are added.

int kruskalMST(int V, int[][] edges) {
    // edges[i] = {u, v, weight}
    Arrays.sort(edges, Comparator.comparingInt(e -> e[2]));

    UnionFind uf = new UnionFind(V);
    int totalWeight = 0, edgesUsed = 0;

    for (int[] edge : edges) {
        int u = edge[0], v = edge[1], w = edge[2];
        if (uf.union(u, v)) {   // false if u and v already connected (would form cycle)
            totalWeight += w;
            edgesUsed++;
            if (edgesUsed == V - 1) break;  // MST complete
        }
    }
    return totalWeight;
}

Application 2: Number of Islands (Alternative to BFS)

For each land cell, union it with adjacent land cells. The number of connected components is the answer.

int numIslands(char[][] grid) {
    int rows = grid.length, cols = grid[0].length;
    UnionFind uf = new UnionFind(rows * cols);
    int waterCount = 0;

    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (grid[r][c] == '0') { waterCount++; continue; }
            int id = r * cols + c;
            // Union with right and down neighbors (avoid double-counting)
            if (r + 1 < rows && grid[r+1][c] == '1') uf.union(id, (r+1)*cols + c);
            if (c + 1 < cols && grid[r][c+1] == '1') uf.union(id, r*cols + (c+1));
        }
    }
    return uf.componentCount() - waterCount;
}

The cell-to-ID mapping r * cols + c is the standard trick for converting 2D grid coordinates to a 1D Union-Find index.

Application 3: Redundant Connection (LC 684)

Given a tree (connected, undirected, V vertices, V-1 edges) with one extra edge added (creating exactly one cycle), find and return the redundant edge.

int[] findRedundantConnection(int[][] edges) {
    int n = edges.length;
    UnionFind uf = new UnionFind(n + 1);  // 1-indexed

    for (int[] edge : edges) {
        if (!uf.union(edge[0], edge[1])) {
            return edge;  // this edge's endpoints were already connected = redundant
        }
    }
    return new int[]{};
}

The first edge where union() returns false is the one that creates the cycle — it’s the redundant connection. This is elegant: Union-Find detects the cycle immediately as it forms.

Practice Problems

#

Problem

Difficulty

Focus

1

LC 547 — Number of Provinces

Medium

Direct DSU: count components

2

LC 684 — Redundant Connection

Medium

Cycle detection with DSU

3

LC 721 — Accounts Merge

Medium

DSU with string-indexed elements

4

LC 1584 — Min Cost to Connect All Points

Medium

Kruskal’s MST

5

LC 1202 — Smallest String With Swaps

Hard

DSU + grouping elements by component

Problem 3 (Accounts Merge) is the tricky one. Elements aren’t integers — they’re email strings. Map each unique email to an integer ID, then run DSU on the IDs. After all unions, group emails by their root component. The challenge is the bookkeeping, not the algorithm.