Lesson 25.1 · Union-Find (DSU)

Find and Union with a Parent Array

Each item points to a parent; the item that points to itself is the group's representative (root). find walks up to the root; union points one root at the other.

14 min

Think of it like this

Clubs at a school, each with a president. Ask any member who their president is and they point you to someone who points you further, until you reach the president. When two clubs merge, one president simply agrees to report to the other.

1.The array and two operations

parent[i] = i at the start: everyone is their own group. find(x) follows parent pointers until parent[r] == r and returns r. union(a, b) finds both roots and, if they differ, sets one root's parent to the other. Two items are connected exactly when their roots are equal.

Without care, the trees can grow into long chains and find becomes O(n). Two fixes, used together, make each operation O(α(n)), which is at most 4 for any realistic n:

Union by size (or rank): attach the smaller tree under the larger one, so depth grows only when sizes double. Path compression: during find, point nodes on the path directly (or closer) to the root, so later finds are shorter.

Main.java

public class Main {
    static int[] parent, size;
    static int groups;

    static int find(int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];   // path halving: point to the grandparent
            x = parent[x];
        }
        return x;
    }

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

    public static void main(String[] args) {
        int n = 6;
        parent = new int[n]; size = new int[n]; groups = n;
        for (int i = 0; i < n; i++) { parent[i] = i; size[i] = 1; }
        union(0, 1); union(2, 3); union(1, 3);
        System.out.println("groups: " + groups);
        System.out.println("0 and 3 connected: " + (find(0) == find(3)));
        System.out.println("size of 0's group: " + size[find(0)]);
        System.out.println("union(0, 2) again: " + union(0, 2));
    }
}

Output

groups: 3
0 and 3 connected: true
size of 0's group: 4
union(0, 2) again: false

▶ Dry run: parent[] through unions and a findn = 6: union(0,1), union(2,3), union(1,3), find(3)

Step 1/5Start: each item is its own root (parent[i] = i).

Remember

Root = representative.
Union by size + path compression → near O(1).
union returning false = already connected (cycle).

Common mistakes

Setting parent[a] = b instead of parent[root(a)] = root(b).
Reading size[] of a non-root.

Words used in this lesson

DSU: Disjoint set union: another name for union-find.
Representative: The root item that names a group.
α(n): The inverse Ackermann function: grows so slowly it's ≤ 4 for any input you'll ever see.

Command Palette

Find and Union with a Parent Array

1.The array and two operations