Union-Find (Disjoint Set Union) Explained with Code

Some problems are about groups that only ever merge: friends of friends become one circle, cables join computers into one network, adjacent land cells form one island. Between the merges you are asked the same question again and again — are these two in the same group? Union-find, also called disjoint set union (DSU), is the data structure built for exactly that: it keeps every group as a small tree in one array, and answers each question and performs each merge in effectively constant time.

Why searching the graph each time is too slow

Picture n computers and a stream of operations: "connect a and b", "can a reach b?". A fresh breadth-first or depth-first search per question costs O(V + E): with 10⁵ computers, cables and questions, up to 2 × 10¹⁰ steps, far beyond the hundred million or so a judge allows in a second. A group label per element makes each question one comparison, but then a merge must relabel a whole group, O(n²) for n merges. Union-find never relabels anyone, and never searches the graph.

The idea: every set is a tree

parent[x] points one step towards the root of x's tree, and a root points at itself. The root is the group's name: two elements are in the same group exactly when they reach the same root. At the start every element is its own one-node tree, parent[i] = i. Three operations work on those trees:

• find(x) follows parent pointers from x to the root and returns it.
• union(a, b) finds both roots. If they differ, it points one root at the other: one assignment merges two whole groups. If they are the same, nothing changes.
• connected(a, b) is find(a) == find(b).

1. Union-find keeps disjoint sets as trees: parent[i] points one step towards the set's root, and a root points at itself. At the start each of the 6 elements is its own set of size 1.
2. union(0, 1): find(0) = 0 and find(1) = 1 are both roots. Sizes 1 and 1 tie, and a tie goes to the first root, so root 1 goes under 0: parent[1] = 0, size[0] = 2. Each root keeps its set's size so the next union knows which tree is bigger.
3. union(2, 3) and union(4, 5) follow the same rule: each joins two single elements, so parent[3] = 2 and parent[5] = 4. That leaves 3 sets: {0, 1}, {2, 3} and {4, 5}.
4. union(1, 3): find(1) walks 1 → 0 and find(3) walks 3 → 2. Sizes 2 and 2 tie again, so root 2 goes under 0: parent[2] = 0, size[0] = 4. A node sinks a level only when its tree is hung under one at least as big, so its set at least doubles each time: no node sinks more than log₂ n levels.
5. connected(3, 5)? find(3) walks 3 → 2 → 0 and find(5) walks 5 → 4. On the way back, path compression points 3 straight at the root: parent[3] = 0. The roots are 0 and 4, so no.
6. union(3, 5): find(3) now takes one hop, 3 → 0, thanks to the compression; find(5) walks 5 → 4. Size 4 beats size 2, so root 4 goes under 0: parent[4] = 0, size[0] = 6. Hanging the smaller tree under the larger leaves the bigger tree's depths alone: only 4 and 5 sink one level.
7. connected(5, 1)? find(5) walks 5 → 4 → 0 and find(1) walks 1 → 0. On the way back, path compression points 5 straight at the root: parent[5] = 0. The roots are both 0, so yes, they are in one set.
8. So connected(5, 1) = true. Every element now points straight at root 0, so any later find is one hop. With union by size and path compression, m operations cost O(m·α(n)), where α stays below 5 for any real n.

Keeping the trees short

Every operation costs as much as a find, and a find costs the depth of the tree. Left to the order of the calls, trees grow into chains. Two tricks prevent that, one in each operation.

Union by size always hangs the root of the smaller tree under the root of the larger one, keeping a size for every root. The same four unions, with and without it:

1. The same 4 unions on 5 elements, twice. On the left every union hangs the second root under the first, whatever the sizes. On the right, union by size hangs the smaller tree under the larger root.
2. union(1, 0): two lone nodes, so both sides hang 0 under 1. So far the rules agree.
3. union(2, 1): the left hangs root 1, and everything under it, below the lone node 2, so 0 sinks a level too. The right compares sizes 1 and 2 and hangs 2 under 1 instead.
4. union(3, 2): the same again. Each union pushes the whole left tree one level down, to 3 links now; the right only adds 3 as one more leaf of root 1.
5. After 4 unions the left is a chain: find(0) walks 4 links, no faster than a list. The right is a star: find(0) takes 1. Every find costs the depth of the tree, so short trees are the whole game.

Why it works is a doubling argument: a node sinks a level only when its tree goes under one at least as big, so its set at least doubles, and a set can double only log₂ n times before it holds everything. No node is ever deeper than log₂ n — 20 levels for a million elements.

1. Union by size merges 8 elements in the pattern that builds the tallest trees it can: always two sets of equal size. Follow element 7, and how deep it sits against how big its set is.
2. union(0, 1), union(2, 3), union(4, 5) and union(6, 7): 7 goes under 6. It sank one level, and the set it now belongs to has 2 elements — twice what it had.
3. union(0, 2) and union(4, 6): 7's whole tree goes under an equal one, so 7 sinks to depth 2 and its set doubles to 4.
4. union(0, 4): 7's whole tree goes under an equal one, so 7 sinks to depth 3 and its set doubles to 8.
5. A node sinks only when its tree goes under one at least as big, so every sink at least doubles its set. A set of 8 allows 3 doublings; a million elements allow 20. No find is ever longer than log₂ n links.

Union by rank compares an upper bound on height instead of the size and gives the same bound; size is handier, because problems often ask how big a group is.

Path compression works inside find. Once the root is known, every node on the walked path is pointed straight at it. That is safe because a node's group is decided by the root it reaches, not by the route it takes — and it means a slow find pays for itself by making the next ones fast.

1. A tall tree, the kind unions build without a size check. find(4) has to climb 4 links to reach the root, 0 — and without help, every later find(4) would climb them all again.
2. find(4) walks 4 → 3 → 2 → 1 → 0 and learns the root. Every node on that walk is in the root's set, whichever route it takes — so it can point straight at the root instead.
3. Path compression does exactly that on the way back: parent[4], parent[3], parent[2] become 0. Node 5 rode along with 3: its depth fell from 4 to 2 without being touched.
4. The next find(5) walks only 5 → 3 → 0 and flattens that too. A slow find pays for itself: now no node is more than 2 links from the root, and the paths it walked are one hop for good.

Each trick alone gives O(log n) per operation. Together, as Robert Tarjan proved in 1975, m operations take O(m α(n)), where α is the inverse Ackermann function — at most 4 for any n that fits in a computer: effectively constant time.

The code

The class also counts the sets: every union that really merges lowers the count, and what is left is the number of connected components — the answer to Number of Provinces.

#include <iostream>
#include <numeric>
#include <utility>
#include <vector>
using namespace std;

class DSU {
public:
    vector<int> parent, size;
    int sets;

    DSU(int n) : parent(n), size(n, 1), sets(n) {
        iota(parent.begin(), parent.end(), 0);   // every element starts as its own root
    }

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

    // Merges the sets of a and b; false when they were already one set.
    // (Named unite because union is a keyword in C++.)
    bool unite(int a, int b) {
        int ra = find(a), rb = find(b);
        if (ra == rb) return false;
        if (size[ra] < size[rb]) swap(ra, rb);   // union by size: small tree under big root
        parent[rb] = ra;
        size[ra] += size[rb];
        sets--;
        return true;
    }

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

int main() {
    DSU dsu(8);
    int edges[][2] = {{0, 1}, {2, 3}, {1, 3}, {4, 5}, {6, 7}, {5, 7}, {3, 0}};
    for (auto& e : edges) {
        cout << "union(" << e[0] << ", " << e[1] << "): ";
        if (dsu.unite(e[0], e[1])) cout << "merged, " << dsu.sets << " sets left\n";
        else cout << "already in one set\n";
    }
    int queries[][2] = {{7, 4}, {1, 6}};
    for (auto& q : queries)
        cout << "connected(" << q[0] << ", " << q[1] << ") = " << (dsu.connected(q[0], q[1]) ? "true" : "false") << "\n";
    cout << "parent after compression:";
    for (int p : dsu.parent) cout << " " << p;
    cout << "\n";
    return 0;
}

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

        DSU(int n) {
            parent = new int[n];
            size = new int[n];
            sets = n;
            for (int i = 0; i < n; i++) {
                parent[i] = i;                   // every element starts as its own root
                size[i] = 1;
            }
        }

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

        // Merges the sets of a and b; false when they were already one set.
        boolean union(int a, int b) {
            int ra = find(a), rb = find(b);
            if (ra == rb) return false;
            if (size[ra] < size[rb]) { int t = ra; ra = rb; rb = t; }  // union by size: small tree under big root
            parent[rb] = ra;
            size[ra] += size[rb];
            sets--;
            return true;
        }

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

    public static void main(String[] args) {
        DSU dsu = new DSU(8);
        int[][] edges = {{0, 1}, {2, 3}, {1, 3}, {4, 5}, {6, 7}, {5, 7}, {3, 0}};
        for (int[] e : edges) {
            String head = "union(" + e[0] + ", " + e[1] + "): ";
            if (dsu.union(e[0], e[1])) System.out.println(head + "merged, " + dsu.sets + " sets left");
            else System.out.println(head + "already in one set");
        }
        int[][] queries = {{7, 4}, {1, 6}};
        for (int[] q : queries)
            System.out.println("connected(" + q[0] + ", " + q[1] + ") = " + dsu.connected(q[0], q[1]));
        StringBuilder line = new StringBuilder("parent after compression:");
        for (int p : dsu.parent) line.append(" ").append(p);
        System.out.println(line);
    }
}

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))  # every element starts as its own root
        self.size = [1] * n
        self.sets = n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # path compression
        return self.parent[x]

    def union(self, a, b):
        """Merge the sets of a and b; False when they were already one set."""
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False
        if self.size[ra] < self.size[rb]:  # union by size: small tree under big root
            ra, rb = rb, ra
        self.parent[rb] = ra
        self.size[ra] += self.size[rb]
        self.sets -= 1
        return True

    def connected(self, a, b):
        return self.find(a) == self.find(b)


dsu = DSU(8)
for a, b in [(0, 1), (2, 3), (1, 3), (4, 5), (6, 7), (5, 7), (3, 0)]:
    if dsu.union(a, b):
        print(f"union({a}, {b}): merged, {dsu.sets} sets left")
    else:
        print(f"union({a}, {b}): already in one set")
for a, b in [(7, 4), (1, 6)]:
    answer = "true" if dsu.connected(a, b) else "false"
    print(f"connected({a}, {b}) = {answer}")
print("parent after compression:", *dsu.parent)

class DSU {
  constructor(n) {
    this.parent = Array.from({ length: n }, (_, i) => i); // every element starts as its own root
    this.size = new Array(n).fill(1);
    this.sets = n;
  }

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

  // Merges the sets of a and b; false when they were already one set.
  union(a, b) {
    let ra = this.find(a);
    let rb = this.find(b);
    if (ra === rb) return false;
    if (this.size[ra] < this.size[rb]) [ra, rb] = [rb, ra]; // union by size: small tree under big root
    this.parent[rb] = ra;
    this.size[ra] += this.size[rb];
    this.sets--;
    return true;
  }

  connected(a, b) {
    return this.find(a) === this.find(b);
  }
}

const dsu = new DSU(8);
for (const [a, b] of [[0, 1], [2, 3], [1, 3], [4, 5], [6, 7], [5, 7], [3, 0]]) {
  if (dsu.union(a, b)) console.log(`union(${a}, ${b}): merged, ${dsu.sets} sets left`);
  else console.log(`union(${a}, ${b}): already in one set`);
}
for (const [a, b] of [[7, 4], [1, 6]]) console.log(`connected(${a}, ${b}) = ${dsu.connected(a, b)}`);
console.log(`parent after compression: ${dsu.parent.join(" ")}`);

union(0, 1): merged, 7 sets left
union(2, 3): merged, 6 sets left
union(1, 3): merged, 5 sets left
union(4, 5): merged, 4 sets left
union(6, 7): merged, 3 sets left
union(5, 7): merged, 2 sets left
union(3, 0): already in one set
connected(7, 4) = true
connected(1, 6) = false
parent after compression: 0 0 0 0 4 4 4 4

Step through the program and match each frame to the line it prints:

1. The first program on 8 elements. Each starts as its own root, so there are 8 sets. Ties in size go the same way every time: the second root goes under the first.
2. union(0, 1): find(0) = 0 and find(1) = 1: two lone roots, so 1 goes under 0. 7 sets left.
3. union(2, 3): find(2) = 2 and find(3) = 3: two lone roots, so 3 goes under 2. 6 sets left.
4. union(1, 3): find(1) walks 1 → 0 and find(3) walks 3 → 2: sizes 2 and 2 tie, so root 2 goes under 0, taking its whole tree along. 5 sets left.
5. union(4, 5): find(4) = 4 and find(5) = 5: two lone roots, so 5 goes under 4. 4 sets left.
6. union(6, 7): find(6) = 6 and find(7) = 7: two lone roots, so 7 goes under 6. 3 sets left.
7. union(5, 7): find(5) walks 5 → 4 and find(7) walks 7 → 6: sizes 2 and 2 tie, so root 6 goes under 4, taking its whole tree along. 2 sets left.
8. union(3, 0): find(3) walks 3 → 2 → 0 and find(0) = 0. Path compression re-points 3 straight at 0. Both roots are 0, so nothing merges — but the find still flattened the path it walked.
9. connected(7, 4): find(7) walks 7 → 6 → 4 and find(4) = 4. Path compression re-points 7 straight at 4. Same root, 4: true.
10. connected(1, 6): find(1) walks 1 → 0 and find(6) walks 6 → 4: different roots, so false. Every element now points straight at its root, [0, 0, 0, 0, 4, 4, 4, 4], so any later find is one hop.

Finding the edge that closes a cycle

A failed union is as useful as a successful one. Union the ends of each edge of an undirected graph in turn; if they already share a root, a path already joined them, so this edge closes a cycle. In Redundant Connection — a tree on nodes 1 to n plus one extra edge, where you return the removable edge that comes last in the input — the first failing edge is the answer: every cycle edge before it was accepted, and it is the one that completes the cycle.

1. A tree on nodes 1 to 5 plus one extra edge; the dashed edges are still to be read, in order. Union each edge's ends as it comes, and watch for the first union that fails.
2. [1, 2]: find(1) = 1 and find(2) = 2, different roots, so no path joins them yet and the edge cannot close a cycle. Union: parent[2] = 1.
3. [2, 3]: find(2) = 1 and find(3) = 3 differ, so the edge joins two separate sets. Union: parent[3] = 1, and the set of 1 is now {1, 2, 3}.
4. [3, 4]: find(3) = 1 and find(4) = 4 differ, so the edge joins two separate sets. Union: parent[4] = 1, and the set of 1 is now {1, 2, 3, 4}.
5. [1, 4]: find(1) = 1 and find(4) = 1, the same root. 1 and 4 were already joined by 1–2–3–4, so this edge closes the cycle and is the answer. [1, 5] is never read.

This version finds the root with path halving: on the way up, each node is re-pointed at its grandparent. It needs no recursion, so a long chain cannot overflow the stack, and the bound is the same.

#include <iostream>
#include <utility>
#include <vector>
using namespace std;

vector<int> parent, sz;

int findRoot(int x) {
    while (parent[x] != x) {
        parent[x] = parent[parent[x]];    // path halving: skip a level on the way up
        x = parent[x];
    }
    return x;
}

// The edge that closes the cycle when a tree on nodes 1..n gets one extra edge.
vector<int> findRedundant(const vector<vector<int>>& edges) {
    int n = edges.size();
    parent.assign(n + 1, 0);               // labels start at 1, so slot 0 is unused
    sz.assign(n + 1, 1);
    for (int i = 0; i <= n; i++) parent[i] = i;
    for (const auto& e : edges) {
        int ra = findRoot(e[0]), rb = findRoot(e[1]);
        if (ra == rb) return e;            // already connected: this edge closes a cycle
        if (sz[ra] < sz[rb]) swap(ra, rb);
        parent[rb] = ra;
        sz[ra] += sz[rb];
    }
    return {};
}

int main() {
    vector<vector<vector<int>>> examples = {
        {{1, 2}, {1, 3}, {2, 3}},
        {{1, 2}, {2, 3}, {3, 4}, {1, 4}, {1, 5}},
    };
    for (const auto& edges : examples) {
        vector<int> e = findRedundant(edges);
        cout << "Redundant edge: [" << e[0] << ", " << e[1] << "]\n";
    }
    return 0;
}

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

    static int findRoot(int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];    // path halving: skip a level on the way up
            x = parent[x];
        }
        return x;
    }

    // The edge that closes the cycle when a tree on nodes 1..n gets one extra edge.
    static int[] findRedundant(int[][] edges) {
        int n = edges.length;
        parent = new int[n + 1];               // labels start at 1, so slot 0 is unused
        size = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
        for (int[] e : edges) {
            int ra = findRoot(e[0]), rb = findRoot(e[1]);
            if (ra == rb) return e;            // already connected: this edge closes a cycle
            if (size[ra] < size[rb]) { int t = ra; ra = rb; rb = t; }
            parent[rb] = ra;
            size[ra] += size[rb];
        }
        return new int[0];
    }

    public static void main(String[] args) {
        int[][][] examples = {
            {{1, 2}, {1, 3}, {2, 3}},
            {{1, 2}, {2, 3}, {3, 4}, {1, 4}, {1, 5}},
        };
        for (int[][] edges : examples) {
            int[] e = findRedundant(edges);
            System.out.println("Redundant edge: [" + e[0] + ", " + e[1] + "]");
        }
    }
}

def find_redundant(edges):
    """The edge that closes the cycle when a tree on nodes 1..n gets one extra edge."""
    n = len(edges)
    parent = list(range(n + 1))  # labels start at 1, so slot 0 is unused
    size = [1] * (n + 1)

    def find_root(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]  # path halving: skip a level on the way up
            x = parent[x]
        return x

    for a, b in edges:
        ra, rb = find_root(a), find_root(b)
        if ra == rb:
            return [a, b]  # already connected: this edge closes a cycle
        if size[ra] < size[rb]:
            ra, rb = rb, ra
        parent[rb] = ra
        size[ra] += size[rb]
    return []


examples = [
    [[1, 2], [1, 3], [2, 3]],
    [[1, 2], [2, 3], [3, 4], [1, 4], [1, 5]],
]
for edges in examples:
    a, b = find_redundant(edges)
    print(f"Redundant edge: [{a}, {b}]")

// The edge that closes the cycle when a tree on nodes 1..n gets one extra edge.
function findRedundant(edges) {
  const n = edges.length;
  const parent = Array.from({ length: n + 1 }, (_, i) => i); // labels start at 1, so slot 0 is unused
  const size = new Array(n + 1).fill(1);

  function findRoot(x) {
    while (parent[x] !== x) {
      parent[x] = parent[parent[x]]; // path halving: skip a level on the way up
      x = parent[x];
    }
    return x;
  }

  for (const [a, b] of edges) {
    let ra = findRoot(a);
    let rb = findRoot(b);
    if (ra === rb) return [a, b]; // already connected: this edge closes a cycle
    if (size[ra] < size[rb]) [ra, rb] = [rb, ra];
    parent[rb] = ra;
    size[ra] += size[rb];
  }
  return [];
}

const examples = [
  [[1, 2], [1, 3], [2, 3]],
  [[1, 2], [2, 3], [3, 4], [1, 4], [1, 5]],
];
for (const edges of examples) {
  const [a, b] = findRedundant(edges);
  console.log(`Redundant edge: [${a}, ${b}]`);
}

Redundant edge: [2, 3]
Redundant edge: [1, 4]

The same test answers Graph Valid Tree: n − 1 edges and no failed union. It needs undirected edges — 0 → 1, 0 → 2 and 1 → 2 hold no directed cycle, yet the third union fails — so for directed graphs use Topological Sort or a DFS with three colours.

Where union-find shows up

• Counting groups: c components need c − 1 extra cables, and every failed union is a spare one you can move.
• Connections over time: sort the logs by time and union until one set is left — dynamic connectivity for a graph that only gains edges.
• Kruskal's algorithm: the Minimum Spanning Tree keeps an edge only if its union succeeds, the cycle test above.
• Offline queries: sort the queries by their limit and union every edge below it before answering connected(p, q).
• Grids: number cell (r, c) as r × cols + c and union neighbours; islands become sets. In Smallest String With Swaps the sets are indices that can swap.

Time and space complexity

Amortised means on average over a sequence: one find can walk a few levels, but it flattens what it walked. Space is O(n). For one question on a fixed graph, a BFS or DFS is just as fast; union-find wins when edges arrive between questions.

How to recognise a union-find problem

• Things join groups through a symmetric, transitive relation: friends of friends, accounts that share an email.
• The question is "are these two connected?" or "how many groups are there?", asked after merges.
• Edges or merges arrive over time, and you want the moment something becomes connected.
• You must find the edge that creates a cycle, or decide whether an undirected graph is a tree.
• Edges are added in sorted order of weight or time, as in Kruskal's algorithm and offline queries.

If it needs a shortest path, a direction or the route itself, use a search: union-find only knows "same set" or not, and cannot split a set once merged.

Common mistakes

• Linking elements instead of roots. parent[a] = b moves a alone and leaves the rest of its tree behind. Always link find(a) to find(b).
• Comparing parents instead of roots. parent[a] == parent[b] misses elements at different depths. Compare find(a) == find(b).
• Counting every union call. Only a union that merges lowers the component count.
• Off-by-one labels. When nodes are labelled 1 to n, allocate n + 1 slots, as the second program does.
• Deep recursion in find. Without union by size, a recursive find on a chain of 10⁵ elements crashes Python. Keep union by size, or use path halving.

Practice in this order

1. Find if Path Exists in Graph: union every edge, then ask one question.
2. Number of Provinces: count the sets, from an adjacency matrix.
3. Number of Connected Components in an Undirected Graph: count the sets, from an edge list.
4. Redundant Connection: the first union that fails.
5. Graph Valid Tree: n − 1 edges and no failed union.
6. Number of Operations to Make Network Connected: count components and spare cables.
7. The Earliest Moment When Everyone Become Friends: unions in time order until one set is left.
8. Min Cost to Connect All Points: union-find inside Kruskal's algorithm.
9. Checking Existence of Edge Length Limited Paths: offline queries sorted by their limit.

The union-find problem list has every problem in the catalogue that uses it. Next on the road is Dijkstra's Algorithm, for the shortest route through a weighted graph.