Union-Find

At a glance

The instinct

Union-Find (Disjoint Set Union, DSU) keeps a forest where every group is a tree and the root is the group's representative. Two operations matter:

• find(x): follow parent pointers up to the root.
• union(a, b): find both roots; if they differ, hang one root under the other.

Reach for it when the problem is about equivalence: "connected", "friends of friends", "same account", "same component". It shines when connections arrive one by one and you must react immediately, for example spotting the first edge that closes a cycle in Redundant Connection.

Recognise it

Not this pattern if...

• You need the actual path or the shortest distance: BFS/DFS.
• Edges are directed and direction matters (prerequisites): Topological Sort.
• Edges get deleted over time: plain DSU cannot split sets (process offline in reverse if possible).
• One static traversal answers everything and the graph is a grid: DFS is often shorter to write.

Memory hack

Analogy: merging clubs. Each club has a president. Asking "are Ana and Raj in the same club?" means asking each for their president and comparing names. Merging clubs means one president agrees to report to the other; members don't need to move.

Say it out loud in the interview:

1. "Each element starts as its own set; I'll map non-integer keys (emails, names) to ids."
2. "For each relation I union the two; union returns false if they were already together."
3. "Find uses path compression and union uses size, so each operation is almost O(1)."

How it works

Trace on 5 nodes with edges (0,1), (2,3), (1,3), (0,2) using union by size:

The last edge is redundant because 0 and 2 were already connected. Running find(3) later climbs 3 → 2 → 0 and, with path compression, rewires 3 straight to 0.

Grouping by keys (Accounts Merge). Give each email an id, union every email in an account with that account's first email, then bucket emails by their root and sort each bucket.

Choosing a victim (Minimize Malware Spread). Union all edges, compute component sizes, count how many initially infected nodes fall in each component, and prefer removing the infected node that is the only infected one in the largest component.

Java template

import java.util.*;

class DSU {
    private final int[] parent, size;
    private int components;

    DSU(int n) {
        parent = new int[n];
        size = new int[n];
        components = n;
        for (int i = 0; i < n; i++) { parent[i] = i; size[i] = 1; }
    }

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

    boolean union(int a, int b) {                       // false = already connected (cycle edge)
        int ra = find(a), rb = find(b);
        if (ra == rb) return false;
        if (size[ra] < size[rb]) { int t = ra; ra = rb; rb = t; }
        parent[rb] = ra;                                // smaller tree under larger
        size[ra] += size[rb];
        components--;
        return true;
    }

    boolean connected(int a, int b) { return find(a) == find(b); }
    int componentSize(int x) { return size[find(x)]; }
    int components() { return components; }
}

class DsuUsage {
    // Map arbitrary keys (emails, names, coordinates) to dense ids first.
    static int idOf(Map<String, Integer> ids, String key) {
        return ids.computeIfAbsent(key, k -> ids.size());
    }

    static int[] firstRedundantEdge(int[][] edges) {    // nodes labelled 1..n
        DSU dsu = new DSU(edges.length + 1);
        for (int[] e : edges) if (!dsu.union(e[0], e[1])) return e;
        return new int[0];
    }
}

Complexity

α is the inverse Ackermann function, which stays below 5 for any realistic input size.

Variations

• Count components: decrement a counter on each successful union. Example: Number of Provinces, Number of Connected Components in an Undirected Graph.
• Cycle detection in undirected graphs: a failed union means a cycle. Example: Redundant Connection, Graph Valid Tree (also require exactly n - 1 edges).
• Grouping by shared keys: union through a hash map of key → id. Example: Accounts Merge.
• Component statistics: track size per root, then reason per component. Example: Minimize Malware Spread.
• Weighted DSU: store a ratio or offset to the parent to answer "a / b = ?" (Evaluate Division style).
• Kruskal's MST: sort edges by weight and union while skipping cycle edges.

Common mistakes

• Comparing parent[a] == parent[b] to test connectivity; parents are not roots. Compare find(a) == find(b).
• Off-by-one with 1-indexed node labels (Redundant Connection uses 1..n); allocate n + 1.
• Skipping both optimisations, which degrades to O(n) per find on adversarial chains.
• Forgetting to map strings or coordinates to integer ids before using arrays.
• Graph Valid Tree: checking only "no cycle" and forgetting that a forest of several trees is also cycle-free; also require one component.

All practice problems

6 problems on this site use this pattern, easiest first. Solve them in order and say the instinct out loud before you code.