Chapter 53 of 65

Disjoint Set Union (Union-Find)

Imagine a new batch of students joining college.

On day one, everyone is a stranger. Then friendships start forming:

Rahul and Priya become friends
Priya and Aman become friends
Sneha and Karan become friends

Now someone asks: "Are Rahul and Aman in the same friend group?"

Yes, because Rahul knows Priya and Priya knows Aman.

"Are Rahul and Sneha in the same group?" No, not yet.

New friendships keep forming, and questions keep coming. We need a data structure that can do two things very fast:

1. Merge two groups         (a new friendship)
2. Check if two people are in the same group

That data structure is the Disjoint Set Union, also called DSU or Union-Find.

A Disjoint Set Union (Union-Find) is a data structure that keeps track of elements divided into non-overlapping groups, and supports merging two groups and finding which group an element belongs to, both in almost constant time.


Why Not Just Use BFS or DFS?

You could store the friendships as a graph and run BFS or DFS to check whether two people are connected.

But each check costs O(V + E). If there are 10⁵ people and 10⁵ questions mixed with new friendships, that is far too slow.

DSU answers each question in almost O(1) time, even while new connections are being added.

Task

BFS / DFS

DSU

Add a connection

O(1)

almost O(1)

Are a and b connected?

O(V + E) per query

almost O(1)

Find the actual path

Yes

No


What Does "Disjoint Set" Mean?

Two sets are disjoint if they have no element in common.

{0, 1, 2}     {3, 4}     {5, 6}

Every element belongs to exactly one set. These sets are disjoint.

DSU supports two main operations:

Operation

What it does

find(x)

Returns the representative (leader) of the set containing x

union(a, b)

Merges the set containing a with the set containing b

Two elements are in the same set if and only if they have the same leader:

connected(a, b) = find(a) == find(b)

Representing Sets as Trees

The clever idea behind DSU is to store each set as a tree. The root of the tree is the leader of the set.

We don't need nodes or pointers. A single array is enough:

parent[x] = the parent of x in its tree

A root is its own parent:

parent[root] == root

For example:

    0         3        5
   / \        |
  1   2       4

index :  0  1  2  3  4  5
parent:  0  0  0  3  3  5

This represents three sets: {0, 1, 2}, {3, 4} and {5}.

To find the leader of 2, follow parents until you reach a root:

2 → parent[2] = 0 → parent[0] = 0 (root)

find(2) = 0

The Basic Version

Initialization

At the start, every element is in its own set. So every element is its own parent.

int[] parent = new int[n];

for (int i = 0; i < n; i++) {
    parent[i] = i;
}
index :  0  1  2  3  4  5  6
parent:  0  1  2  3  4  5  6

Find

Walk up until you reach the root.

int find(int x) {

    while (parent[x] != x) {
        x = parent[x];
    }

    return x;
}

Union

Find both roots. If they are different, make one root the parent of the other.

void union(int a, int b) {

    int rootA = find(a);
    int rootB = find(b);

    if (rootA != rootB) {
        parent[rootA] = rootB;
    }
}

Notice that we connect the roots, not a and b themselves. This is very important, and a common mistake.


The Problem: Tall Trees

The basic version works, but it can become slow.

Suppose we do:

union(0, 1)
union(1, 2)
union(2, 3)
union(3, 4)

With the basic union, every time the old root is attached below the new one, we get a long chain:

4
|
3
|
2
|
1
|
0

Now find(0) has to walk through every element. With n elements, one find can cost O(n). This is no better than a linked list.

Two simple tricks fix this completely:

1. Path Compression    (makes find flatten the tree)
2. Union by Size/Rank  (keeps trees short when merging)

Optimization 1: Path Compression

When we call find(x), we walk through every node on the path to the root.

Since we have found the root anyway, why not make every one of those nodes point directly to the root? Next time, their find will take just one step.

int find(int x) {

    if (parent[x] != x) {
        parent[x] = find(parent[x]);
    }

    return parent[x];
}

The recursive call finds the root, and on the way back, every node on the path is attached directly to it.

Before and after find(0) on the chain:

Before:                After:

4                          4
|                     /  /   \  \
3                    0  1     2  3
|
2
|
1
|
0

Let's see it happen in code. This program builds the chain with the basic union, then calls the path-compression find once.

import java.util.Arrays;

class Main {

    static int[] parent;

    // Naive find: just walk up to the root
    static int findNaive(int x) {

        while (parent[x] != x) {
            x = parent[x];
        }

        return x;
    }

    // Find with path compression
    static int find(int x) {

        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }

        return parent[x];
    }

    public static void main(String[] args) {

        int n = 5;
        parent = new int[n];

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

        // Naive union that always attaches the first root under the second
        for (int i = 0; i < n - 1; i++) {
            parent[findNaive(i)] = findNaive(i + 1);
        }

        System.out.println("Before: " + Arrays.toString(parent));

        System.out.println("find(0) = " + find(0));

        System.out.println("After:  " + Arrays.toString(parent));
    }
}

Output:

Before: [1, 2, 3, 4, 4]
find(0) = 4
After:  [4, 4, 4, 4, 4]

One call to find(0) flattened the entire chain. Every element now points straight at the root 4.


Optimization 2: Union by Size (or Rank)

Path compression fixes trees after they become tall. Union by size stops them from becoming tall in the first place.

The idea: when merging two trees, attach the smaller tree under the root of the larger tree.

Tree A (size 3)      Tree B (size 1)

    0                     5
   / \
  1   2

Attach smaller under larger:

    0
  / | \
 1  2  5

If we did it the other way round, every node of the bigger tree would become one level deeper.

We keep a size[] array, where size[root] is the number of elements in that root's set:

void union(int a, int b) {

    int rootA = find(a);
    int rootB = find(b);

    if (rootA == rootB) {
        return;
    }

    if (size[rootA] < size[rootB]) {
        parent[rootA] = rootB;
        size[rootB] += size[rootA];
    } else {
        parent[rootB] = rootA;
        size[rootA] += size[rootB];
    }
}

With union by size, a tree with n elements can never be taller than about log₂ n. An element only moves one level deeper when its tree is merged into a tree at least as big, so its set size at least doubles each time, and that can happen at most log₂ n times.

Union by Rank

Many books use rank instead of size. Rank is an upper bound on the height of the tree.

Attach the root with smaller rank under the root with larger rank.
If both ranks are equal, attach either one and increase the new root's rank by 1.

Union by size and union by rank give the same time complexity. Size is often more useful, because you can also answer "how big is this group?" directly.


Time Complexity

Version

Cost per operation

Basic (no optimization)

O(n) worst case

Union by size/rank only

O(log n) worst case

Path compression only

O(log n) amortized

Both together

O(α(n)) amortized

α(n) is the inverse Ackermann function. It grows so slowly that it is at most 4 for any input size that could ever fit in a computer.

So in practice:

With path compression and union by size/rank, each DSU operation takes almost constant time.

"Amortized" means averaged over a sequence of operations. A single find can occasionally take longer, but it flattens the tree so that later operations are faster.

Space complexity is O(n) for the parent[] and size[] arrays.


A Complete DSU Class in Java

Here is a reusable DSU with both optimizations. union() returns false if the two elements were already in the same set, which is very handy in problems.

class DisjointSet {

    private int[] parent;
    private int[] size;
    private int components;

    DisjointSet(int n) {

        parent = new int[n];
        size = new int[n];
        components = n;

        for (int i = 0; i < n; i++) {
            parent[i] = i;   // every element is its own leader
            size[i] = 1;
        }
    }

    // Find with path compression
    int find(int x) {

        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }

        return parent[x];
    }

    // Union by size: attach the smaller tree under the larger one
    boolean union(int a, int b) {

        int rootA = find(a);
        int rootB = find(b);

        if (rootA == rootB) {
            return false;   // already in the same set
        }

        if (size[rootA] < size[rootB]) {
            int temp = rootA;
            rootA = rootB;
            rootB = temp;
        }

        parent[rootB] = rootA;
        size[rootA] += size[rootB];
        components--;

        return true;
    }

    boolean connected(int a, int b) {
        return find(a) == find(b);
    }

    int sizeOf(int x) {
        return size[find(x)];
    }

    int getComponents() {
        return components;
    }
}

class Main {

    public static void main(String[] args) {

        DisjointSet ds = new DisjointSet(7);

        ds.union(0, 1);
        ds.union(1, 2);
        ds.union(3, 4);
        ds.union(5, 6);

        System.out.println("0 and 2 connected: " + ds.connected(0, 2));
        System.out.println("0 and 3 connected: " + ds.connected(0, 3));
        System.out.println("4 and 6 connected: " + ds.connected(4, 6));
        System.out.println("Components: " + ds.getComponents());

        ds.union(4, 6);

        System.out.println("After union(4, 6):");
        System.out.println("4 and 6 connected: " + ds.connected(4, 6));
        System.out.println("Size of 3's set: " + ds.sizeOf(3));
        System.out.println("Components: " + ds.getComponents());

        System.out.println("union(0, 2) again: " + ds.union(0, 2));
    }
}

Output:

0 and 2 connected: true
0 and 3 connected: false
4 and 6 connected: false
Components: 3
After union(4, 6):
4 and 6 connected: true
Size of 3's set: 4
Components: 2
union(0, 2) again: false

Step-by-Step Trace

Let's follow the parent and size arrays for the program above.

Start:

index :  0  1  2  3  4  5  6
parent:  0  1  2  3  4  5  6
size  :  1  1  1  1  1  1  1
components = 7

union(0, 1): roots are 0 and 1, sizes are equal, so 1 goes under 0.

parent:  0  0  2  3  4  5  6
size[0] = 2, components = 6

union(1, 2): find(1) = 0, find(2) = 2. Size 2 vs size 1, so 2 goes under 0.

parent:  0  0  0  3  4  5  6
size[0] = 3, components = 5

union(3, 4) and union(5, 6):

parent:  0  0  0  3  3  5  5
size[3] = 2, size[5] = 2, components = 3

    0         3       5
   / \        |       |
  1   2       4       6

union(4, 6): find(4) = 3, find(6) = 5. Both sizes are 2, so root 5 goes under root 3.

parent:  0  0  0  3  3  3  5
size[3] = 4, components = 2

    0           3
   / \         / \
  1   2       4   5
                  |
                  6

Finally, union(0, 2) finds the same root 0 for both, so it returns false and nothing changes.

Note that size[] is only meaningful for roots. That is why sizeOf(x) returns size[find(x)].


Application 1: Cycle Detection in an Undirected Graph

In the Cycle Detection chapter, we used DFS with a parent check. DSU gives another, very elegant method.

Process the edges one by one:

For each edge (u, v):
    if find(u) == find(v):
        u and v are already connected
        → this edge creates a CYCLE
    else:
        union(u, v)

If u and v are already connected by some path, adding a direct edge between them closes a loop.

This is exactly the LeetCode problem Redundant Connection (684): a tree with n vertices (numbered 1 to n) had one extra edge added. Return the edge that can be removed so the graph becomes a tree again. If there are several answers, return the one that appears last in the input.

import java.util.Arrays;

class Main {

    static int[] parent;
    static int[] size;

    static int find(int x) {

        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }

        return parent[x];
    }

    static boolean union(int a, int b) {

        int rootA = find(a);
        int rootB = find(b);

        if (rootA == rootB) {
            return false;
        }

        if (size[rootA] < size[rootB]) {
            int temp = rootA;
            rootA = rootB;
            rootB = temp;
        }

        parent[rootB] = rootA;
        size[rootA] += size[rootB];

        return true;
    }

    // Vertices are numbered 1..n, so arrays have size n + 1
    static int[] findRedundantConnection(int[][] edges) {

        int n = edges.length;

        parent = new int[n + 1];
        size = new int[n + 1];

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

        for (int[] edge : edges) {

            // both ends already connected: this edge makes a cycle
            if (!union(edge[0], edge[1])) {
                return edge;
            }
        }

        return new int[0];
    }

    public static void main(String[] args) {

        int[][] edges1 = {{1, 2}, {1, 3}, {2, 3}};
        int[][] edges2 = {{1, 2}, {2, 3}, {3, 4}, {1, 4}, {1, 5}};

        System.out.println(Arrays.toString(findRedundantConnection(edges1)));
        System.out.println(Arrays.toString(findRedundantConnection(edges2)));
    }
}

Output:

[2, 3]
[1, 4]

In the second example, after 1-2, 2-3 and 3-4, vertices 1 and 4 are already connected. So the edge [1, 4] creates the cycle 1 → 2 → 3 → 4 → 1.

Because the graph has exactly one extra edge, the first edge that closes a cycle is also the last edge of that cycle in the input, which is what the problem asks for.

Remember: this method works only for undirected graphs. DSU has no idea about edge direction.


Application 2: Counting Connected Components

Start with n components. Every successful union merges two components into one, so the count goes down by 1.

That is exactly what the components counter in our class does.

The problem Number of Provinces (LeetCode 547) gives an adjacency matrix isConnected, and asks how many groups of connected cities there are:

static int findCircleNum(int[][] isConnected) {

    int n = isConnected.length;
    DisjointSet ds = new DisjointSet(n);

    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (isConnected[i][j] == 1) {
                ds.union(i, j);
            }
        }
    }

    return ds.getComponents();
}

For {{1, 1, 0}, {1, 1, 0}, {0, 0, 1}} this returns 2: cities 0 and 1 form one province, and city 2 is alone.

You could solve this with DFS too. DSU really shines when connections arrive one at a time and you must answer questions in between.


Application 3: Kruskal's Algorithm

In the next chapter, you will learn Kruskal's algorithm for finding a minimum spanning tree.

It goes through edges from cheapest to most expensive and keeps an edge only if it does not create a cycle. That check is exactly find(u) != find(v).

So DSU is the engine that makes Kruskal's algorithm fast.


More Places Where DSU Is Used

  • Social networks: are two users in the same friend circle?

  • Network connectivity: are two computers connected, as cables are added?

  • Image processing: grouping connected pixels into regions.

  • Accounts Merge (LeetCode 721): accounts sharing an email belong to the same person.

  • Satisfiability of Equality Equations (LeetCode 990): union all a == b, then check that no a != b has both sides in the same set.

  • Number of Operations to Make Network Connected (LeetCode 1319): the answer is components - 1, as long as there are at least n - 1 cables.


Limitations of DSU

DSU is very fast, but it can only do a few things.

  • No splitting. You can merge sets, but you cannot easily remove an edge or split a set.

  • No paths. It tells you whether two elements are connected, not how.

  • Undirected only. "Connected" in DSU is symmetric, so it cannot model one-way edges.

If you need any of these, use BFS or DFS instead.


Common Mistakes

1. Comparing parents instead of roots

// WRONG
if (parent[a] == parent[b])

// CORRECT
if (find(a) == find(b))

Two elements can be in the same set while having different direct parents.

2. Linking the elements instead of their roots

// WRONG
parent[a] = b;

// CORRECT
parent[find(a)] = find(b);

Setting parent[a] = b cuts a away from its old tree and can split sets apart.

3. Forgetting to initialize

Every element must start with parent[i] = i. A fresh Java int[] is all zeros, which means everyone points to 0.

4. Wrong array size for 1-indexed input

If vertices are numbered 1 to n, create arrays of size n + 1.

5. Reading size[] of a non-root

size[x] is only correct when x is a root. Always use size[find(x)].

6. Recursion depth

The recursive find is safe when you also use union by size, because trees stay at most about log₂ n tall. Without it, the first find on a long chain can cause a StackOverflowError. An iterative version avoids this completely:

int find(int x) {

    int root = x;

    while (parent[root] != root) {
        root = parent[root];
    }

    // second pass: point every node on the path to the root
    while (parent[x] != root) {
        int next = parent[x];
        parent[x] = root;
        x = next;
    }

    return root;
}

Practice Problems

  • Number of Provinces (LeetCode 547)

  • Redundant Connection (LeetCode 684)

  • Number of Operations to Make Network Connected (LeetCode 1319)

  • Satisfiability of Equality Equations (LeetCode 990)

  • Accounts Merge (LeetCode 721)

  • Most Stones Removed with Same Row or Column (LeetCode 947)

  • Disjoint Set (Union-Find) (GeeksforGeeks), implement find and union


Interview Tips

  • Keep a DSU template ready. In an interview, you should be able to write find with path compression and union by size in under two minutes.

  • Hints that a problem wants DSU: "groups", "connected", "merge", "same component", "redundant edge", or connections that arrive one by one.

  • Mention both optimizations and the O(α(n)) complexity. Interviewers like hearing that it is "almost constant".

  • If the elements are strings (like emails), map each one to an integer index with a HashMap first.


The Main Idea

Disjoint Set Union keeps elements in separate groups and supports two operations:

find(x)      → leader of x's group
union(a, b)  → merge the groups of a and b

Each group is stored as a tree inside a parent[] array, with the root as the leader.

Two optimizations make it extremely fast:

Path Compression  → find() points every node on the path to the root
Union by Size     → attach the smaller tree under the larger one

Together:

Time  → O(α(n)) amortized per operation (almost constant)
Space → O(n)

When a problem keeps merging groups and asking "are these two connected?", reach for Union-Find.

In the next chapter, DSU will help us build the cheapest possible network using Kruskal's algorithm.