PK

PKBytes

Explore tracks
Chapter 31: Disjoint Set Union (Union-Find)
31.03Intermediate / Advanced5 topics16 min5 interactive animations

DSU problem patterns

The classic union-find problems: provinces, the redundant edge, merging accounts by shared emails, Kruskal's minimum spanning tree and counting islands as land is added.

Learning goals

  • Count components and detect the edge that closes a cycle
  • Group items that share a key by uniting them through the key
  • Build a minimum spanning tree with Kruskal's algorithm
  • Maintain an island count while cells are added

Prerequisites

DSU modelOptimizationsSortingGraph basics

All of these problems say the same thing in different words: 'these two belong together'. Each time you see a stream of such statements and a question about the groups, union-find is the first tool to reach for.

31.03.1

Number of provinces

Given an n × n matrix where isConnected[i][j] = 1 means cities i and j are directly connected, a **province** is a set of cities connected directly or indirectly. That is a connected component, so start with n provinces and subtract one for every successful union over the 1-entries (the matrix is symmetric, so visiting j > i is enough). A depth-first search works too; union-find needs no recursion and handles edges arriving one by one.

The cost is O(n² α(n)) for reading the matrix. Notice the pattern that repeats in this lesson: if (d.union(a, b)) count--. The return value of union carries the information.

Java
1static class DSU {
2    final int[] parent, size;
3    DSU(int n) { parent = new int[n]; size = new int[n]; for (int i = 0; i < n; i++) { parent[i] = i; size[i] = 1; } }
4    int find(int x) { while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; } return x; }   // path halving
5    boolean union(int a, int b) {                // false if a and b were already connected
6        int ra = find(a), rb = find(b);
7        if (ra == rb) return false;
8        if (size[ra] < size[rb]) { int t = ra; ra = rb; rb = t; }
9        parent[rb] = ra; size[ra] += size[rb];
10        return true;
11    }
12}
13
14static int findCircleNum(int[][] isConnected) {
15    int n = isConnected.length;
16    DSU d = new DSU(n);
17    int provinces = n;
18    for (int i = 0; i < n; i++)
19        for (int j = i + 1; j < n; j++)
20            if (isConnected[i][j] == 1 && d.union(i, j)) provinces--;      // each merge removes one province
21    return provinces;
22}

Union-find on edges: components, redundant edge, Kruskal

Interactive · edit the input

Your input

Try

disjoint-set forest (arrow = parent, roots on top) · 6 nodes

0
1
2
3
4
5
Edge kept (joins two sets)Edge skipped (same set)Edge being testedNot tested yetA root

edges in the order given

0-11
1-22
3-43
2-04
4-55
Setup

Start with n components, one per vertex. Every edge whose endpoints are in different sets merges two components (count - 1); an edge inside one set changes nothing.

Step 1 / 7
Java
1int countComponents(int n, int[][] edges) {
2    DSU d = new DSU(n); int comps = n;
3    for (int[] e : edges) if (d.union(e[0], e[1])) comps--;       // a successful union merges two components
4    return comps;
5}
6int[] firstCycleEdge(int n, int[][] edges) {     // the first edge whose endpoints are already connected
7    DSU d = new DSU(n);
8    for (int[] e : edges) if (!d.union(e[0], e[1])) return e;
9    return null;
10}
11long kruskal(int n, int[][] edges) {             // edges are {a, b, w}
12    int[][] sorted = edges.clone();
13    Arrays.sort(sorted, Comparator.comparingInt(e -> e[2]));      // stable: ties keep the input order
14    DSU d = new DSU(n); long total = 0;
15    for (int[] e : sorted) if (d.union(e[0], e[1])) total += e[2];   // keep an edge only if it joins two components
16    return total;
17}

Live state

0 edges kept0 edges skipped6 components

vertices

6

edges

5

No condition evaluated on this step
Execution trace (dry run table)Show 7 steps
StepLineStateWhat happens
1L1vertices=6 edges=5Start with n components, one per vertex. Every edge whose endpoints are in different sets merges two components (count - 1); an edge inside one set changes nothing.
2L3edge=0-1 components=5Edge 0-1 joins the sets of roots 0 and 1: 5 components left.
3L3edge=1-2 components=4Edge 1-2 joins the sets of roots 0 and 2: 4 components left.
4L3edge=3-4 components=3Edge 3-4 joins the sets of roots 3 and 4: 3 components left.
5L3edge=2-0 root of a=0 root of b=0Edge 2-0: both ends have root 0, so they are already connected. Skip it.
6L3edge=4-5 components=2Edge 4-5 joins the sets of roots 3 and 5: 2 components left.
7L4return=22 connected components (provinces). The edges kept form a spanning forest with 4 edges.
31.03.2

Redundant connection

A tree on n vertices has n - 1 edges. If one extra edge is added, exactly one edge can be removed to get a tree again: the extra edge closes a cycle. Process the edges in order with a union-find: the first edge whose two endpoints are already connected (union returns false) closes a cycle, and it is redundant. In LeetCode's version (a tree plus one extra edge) this is exactly the expected answer: the first edge that closes a cycle is the last edge of that cycle in input order.

In the animation's "Redundant connection" preset, 0-1 1-2 2-3 3-4 4-1 0-4 is processed in order: 4-1 is the first edge whose ends already share a root (1 reaches 4 through 2, 3), so it is reported. A search would have to explore the graph for each edge; the union-find answers each edge in near-constant time.

Java
1static class DSU {
2    final int[] parent, size;
3    DSU(int n) { parent = new int[n]; size = new int[n]; for (int i = 0; i < n; i++) { parent[i] = i; size[i] = 1; } }
4    int find(int x) { while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; } return x; }   // path halving
5    boolean union(int a, int b) {                // false if a and b were already connected
6        int ra = find(a), rb = find(b);
7        if (ra == rb) return false;
8        if (size[ra] < size[rb]) { int t = ra; ra = rb; rb = t; }
9        parent[rb] = ra; size[ra] += size[rb];
10        return true;
11    }
12}
13
14static int[] firstCycleEdge(int n, int[][] edges) {      // the first edge whose endpoints are already connected
15    DSU d = new DSU(n);
16    for (int[] e : edges)
17        if (!d.union(e[0], e[1])) return e;
18    return null;                                 // the edges form a forest
19}

Union-find on edges: components, redundant edge, Kruskal

Interactive · edit the input

Your input

Try

disjoint-set forest (arrow = parent, roots on top) · 6 nodes

0
1
2
3
4
5
Edge kept (joins two sets)Edge skipped (same set)Edge being testedNot tested yetA root

edges in the order given

0-11
1-22
3-43
2-04
4-55
Setup

Start with n components, one per vertex. Every edge whose endpoints are in different sets merges two components (count - 1); an edge inside one set changes nothing.

Step 1 / 7
Java
1int countComponents(int n, int[][] edges) {
2    DSU d = new DSU(n); int comps = n;
3    for (int[] e : edges) if (d.union(e[0], e[1])) comps--;       // a successful union merges two components
4    return comps;
5}
6int[] firstCycleEdge(int n, int[][] edges) {     // the first edge whose endpoints are already connected
7    DSU d = new DSU(n);
8    for (int[] e : edges) if (!d.union(e[0], e[1])) return e;
9    return null;
10}
11long kruskal(int n, int[][] edges) {             // edges are {a, b, w}
12    int[][] sorted = edges.clone();
13    Arrays.sort(sorted, Comparator.comparingInt(e -> e[2]));      // stable: ties keep the input order
14    DSU d = new DSU(n); long total = 0;
15    for (int[] e : sorted) if (d.union(e[0], e[1])) total += e[2];   // keep an edge only if it joins two components
16    return total;
17}

Live state

0 edges kept0 edges skipped6 components

vertices

6

edges

5

No condition evaluated on this step
Execution trace (dry run table)Show 7 steps
StepLineStateWhat happens
1L1vertices=6 edges=5Start with n components, one per vertex. Every edge whose endpoints are in different sets merges two components (count - 1); an edge inside one set changes nothing.
2L3edge=0-1 components=5Edge 0-1 joins the sets of roots 0 and 1: 5 components left.
3L3edge=1-2 components=4Edge 1-2 joins the sets of roots 0 and 2: 4 components left.
4L3edge=3-4 components=3Edge 3-4 joins the sets of roots 3 and 4: 3 components left.
5L3edge=2-0 root of a=0 root of b=0Edge 2-0: both ends have root 0, so they are already connected. Skip it.
6L3edge=4-5 components=2Edge 4-5 joins the sets of roots 3 and 5: 2 components left.
7L4return=22 connected components (provinces). The edges kept form a spanning forest with 4 edges.
31.03.3

Accounts merge

Each account has a name and a list of emails. Two accounts belong to the same person if they share an email, even indirectly (A shares with B and B with C). Treat accounts as elements: whenever an email is seen for the second time, unite the current account with the account that had it first. Afterwards group all emails by the representative of their account, sort them, and put the name first.

The key idea is to unite through a shared key. A map from email to the first account index does the lookup in O(1), so the whole merge is near-linear in the total number of emails (plus the sorting of each group). Names do not decide anything: two different people may have the same name.

Java
1static class DSU {
2    final int[] parent, size;
3    DSU(int n) { parent = new int[n]; size = new int[n]; for (int i = 0; i < n; i++) { parent[i] = i; size[i] = 1; } }
4    int find(int x) { while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; } return x; }   // path halving
5    boolean union(int a, int b) {                // false if a and b were already connected
6        int ra = find(a), rb = find(b);
7        if (ra == rb) return false;
8        if (size[ra] < size[rb]) { int t = ra; ra = rb; rb = t; }
9        parent[rb] = ra; size[ra] += size[rb];
10        return true;
11    }
12}
13
14static List<List<String>> accountsMerge(List<List<String>> accounts) {
15    int n = accounts.size();
16    DSU d = new DSU(n);
17    Map<String, Integer> owner = new HashMap<>();              // email -> the first account that had it
18    for (int i = 0; i < n; i++)
19        for (int k = 1; k < accounts.get(i).size(); k++) {
20            Integer j = owner.putIfAbsent(accounts.get(i).get(k), i);
21            if (j != null) d.union(i, j);        // the same email in two accounts: one person
22        }
23    Map<Integer, TreeSet<String>> emails = new HashMap<>();
24    for (Map.Entry<String, Integer> e : owner.entrySet())
25        emails.computeIfAbsent(d.find(e.getValue()), k -> new TreeSet<>()).add(e.getKey());
26    List<List<String>> out = new ArrayList<>();
27    for (Map.Entry<Integer, TreeSet<String>> e : emails.entrySet()) {
28        List<String> row = new ArrayList<>();
29        row.add(accounts.get(e.getKey()).get(0));
30        row.addAll(e.getValue());
31        out.add(row);
32    }
33    return out;
34}

Union-find on edges: components, redundant edge, Kruskal

Interactive · edit the input

Your input

Try

disjoint-set forest (arrow = parent, roots on top) · 6 nodes

0
1
2
3
4
5
Edge kept (joins two sets)Edge skipped (same set)Edge being testedNot tested yetA root

edges in the order given

0-11
1-22
3-43
2-04
4-55
Setup

Start with n components, one per vertex. Every edge whose endpoints are in different sets merges two components (count - 1); an edge inside one set changes nothing.

Step 1 / 7
Java
1int countComponents(int n, int[][] edges) {
2    DSU d = new DSU(n); int comps = n;
3    for (int[] e : edges) if (d.union(e[0], e[1])) comps--;       // a successful union merges two components
4    return comps;
5}
6int[] firstCycleEdge(int n, int[][] edges) {     // the first edge whose endpoints are already connected
7    DSU d = new DSU(n);
8    for (int[] e : edges) if (!d.union(e[0], e[1])) return e;
9    return null;
10}
11long kruskal(int n, int[][] edges) {             // edges are {a, b, w}
12    int[][] sorted = edges.clone();
13    Arrays.sort(sorted, Comparator.comparingInt(e -> e[2]));      // stable: ties keep the input order
14    DSU d = new DSU(n); long total = 0;
15    for (int[] e : sorted) if (d.union(e[0], e[1])) total += e[2];   // keep an edge only if it joins two components
16    return total;
17}

Live state

0 edges kept0 edges skipped6 components

vertices

6

edges

5

No condition evaluated on this step
Execution trace (dry run table)Show 7 steps
StepLineStateWhat happens
1L1vertices=6 edges=5Start with n components, one per vertex. Every edge whose endpoints are in different sets merges two components (count - 1); an edge inside one set changes nothing.
2L3edge=0-1 components=5Edge 0-1 joins the sets of roots 0 and 1: 5 components left.
3L3edge=1-2 components=4Edge 1-2 joins the sets of roots 0 and 2: 4 components left.
4L3edge=3-4 components=3Edge 3-4 joins the sets of roots 3 and 4: 3 components left.
5L3edge=2-0 root of a=0 root of b=0Edge 2-0: both ends have root 0, so they are already connected. Skip it.
6L3edge=4-5 components=2Edge 4-5 joins the sets of roots 3 and 5: 2 components left.
7L4return=22 connected components (provinces). The edges kept form a spanning forest with 4 edges.
31.03.4

Kruskal

**Kruskal's algorithm** builds a minimum spanning tree by sorting the edges by weight and keeping an edge exactly when it joins two different components. Union-find is the cycle test: union returns false when both ends are already connected. After at most n - 1 kept edges the tree is complete; on a disconnected graph the result is a minimum spanning forest.

Try the preset "Kruskal" (0-1:4 0-2:1 1-2:2 1-3:5 2-3:8 3-4:3 2-4:9): the sorted edges are tried in order, 0-2:1, 1-2:2, 3-4:3 and 0-1:4 (skipped, 0 and 1 are already connected), then 1-3:5 completes the tree. The total weight is 11. The cost is O(E log E) for the sort plus near-constant union-find work.

Java
1static class DSU {
2    final int[] parent, size;
3    DSU(int n) { parent = new int[n]; size = new int[n]; for (int i = 0; i < n; i++) { parent[i] = i; size[i] = 1; } }
4    int find(int x) { while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; } return x; }   // path halving
5    boolean union(int a, int b) {                // false if a and b were already connected
6        int ra = find(a), rb = find(b);
7        if (ra == rb) return false;
8        if (size[ra] < size[rb]) { int t = ra; ra = rb; rb = t; }
9        parent[rb] = ra; size[ra] += size[rb];
10        return true;
11    }
12}
13
14static long kruskal(int n, int[][] edges) {      // edges are {a, b, w}; returns the weight of a minimum spanning forest
15    int[][] sorted = edges.clone();
16    Arrays.sort(sorted, Comparator.comparingInt(e -> e[2]));         // stable: ties keep the input order
17    DSU d = new DSU(n);
18    long total = 0;
19    for (int[] e : sorted)
20        if (d.union(e[0], e[1])) total += e[2];  // keep an edge only if it joins two components
21    return total;
22}

Union-find on edges: components, redundant edge, Kruskal

Interactive · edit the input

Your input

Try

disjoint-set forest (arrow = parent, roots on top) · 6 nodes

0
1
2
3
4
5
Edge kept (joins two sets)Edge skipped (same set)Edge being testedNot tested yetA root

edges in the order given

0-11
1-22
3-43
2-04
4-55
Setup

Start with n components, one per vertex. Every edge whose endpoints are in different sets merges two components (count - 1); an edge inside one set changes nothing.

Step 1 / 7
Java
1int countComponents(int n, int[][] edges) {
2    DSU d = new DSU(n); int comps = n;
3    for (int[] e : edges) if (d.union(e[0], e[1])) comps--;       // a successful union merges two components
4    return comps;
5}
6int[] firstCycleEdge(int n, int[][] edges) {     // the first edge whose endpoints are already connected
7    DSU d = new DSU(n);
8    for (int[] e : edges) if (!d.union(e[0], e[1])) return e;
9    return null;
10}
11long kruskal(int n, int[][] edges) {             // edges are {a, b, w}
12    int[][] sorted = edges.clone();
13    Arrays.sort(sorted, Comparator.comparingInt(e -> e[2]));      // stable: ties keep the input order
14    DSU d = new DSU(n); long total = 0;
15    for (int[] e : sorted) if (d.union(e[0], e[1])) total += e[2];   // keep an edge only if it joins two components
16    return total;
17}

Live state

0 edges kept0 edges skipped6 components

vertices

6

edges

5

No condition evaluated on this step
Execution trace (dry run table)Show 7 steps
StepLineStateWhat happens
1L1vertices=6 edges=5Start with n components, one per vertex. Every edge whose endpoints are in different sets merges two components (count - 1); an edge inside one set changes nothing.
2L3edge=0-1 components=5Edge 0-1 joins the sets of roots 0 and 1: 5 components left.
3L3edge=1-2 components=4Edge 1-2 joins the sets of roots 0 and 2: 4 components left.
4L3edge=3-4 components=3Edge 3-4 joins the sets of roots 3 and 4: 3 components left.
5L3edge=2-0 root of a=0 root of b=0Edge 2-0: both ends have root 0, so they are already connected. Skip it.
6L3edge=4-5 components=2Edge 4-5 joins the sets of roots 3 and 5: 2 components left.
7L4return=22 connected components (provinces). The edges kept form a spanning forest with 4 edges.
31.03.5

Dynamic island additions

'Number of Islands II' adds land cells to an initially empty grid, one at a time, and asks for the number of islands after each addition. A search from scratch after every step would cost O(R × C) each. With a union-find over all cells, adding land is: islands + 1, then for each of the four neighbours that is already land, a successful union means two islands merged and islands - 1.

A repeated cell must be ignored, since it is already land: the preset "A repeated cell changes nothing" shows 0,0 added twice. In "One cell joins four islands" the cells 0,1 1,0 1,2 2,1 give counts 1, 2, 3, 4, and adding the centre 1,1 merges all four: the count drops to 1. Each addition is O(α) per neighbour.

Java
1static class DSU {
2    final int[] parent, size;
3    DSU(int n) { parent = new int[n]; size = new int[n]; for (int i = 0; i < n; i++) { parent[i] = i; size[i] = 1; } }
4    int find(int x) { while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; } return x; }   // path halving
5    boolean union(int a, int b) {                // false if a and b were already connected
6        int ra = find(a), rb = find(b);
7        if (ra == rb) return false;
8        if (size[ra] < size[rb]) { int t = ra; ra = rb; rb = t; }
9        parent[rb] = ra; size[ra] += size[rb];
10        return true;
11    }
12}
13
14static final int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
15static List<Integer> numIslands2(int R, int C, int[][] positions) {
16    DSU d = new DSU(R * C);
17    boolean[] land = new boolean[R * C];
18    List<Integer> out = new ArrayList<>();
19    int islands = 0;
20    for (int[] p : positions) {
21        int id = p[0] * C + p[1];
22        if (!land[id]) {                         // a repeated cell changes nothing
23            land[id] = true;
24            islands++;
25            for (int[] dir : DIRS) {
26                int nr = p[0] + dir[0], nc = p[1] + dir[1];
27                if (nr >= 0 && nc >= 0 && nr < R && nc < C && land[nr * C + nc] && d.union(id, nr * C + nc)) islands--;   // merge neighbours
28            }
29        }
30        out.add(islands);
31    }
32    return out;
33}

Number of Islands II: add land one cell at a time

Interactive · edit the input

Your input

Try

grid · 3 × 4

0123
0
·
·
·
·
1
·
·
·
·
2
·
·
·
·
Cell just addedIsland merged into this oneLand (number = island id)Water

islands after each addition

none
Setup

Every cell is its own set in a union-find over all R × C cells, but only land cells count. Adding land makes one new island; each adjacent land cell in a different set merges two islands and removes one. Each addition costs a few near-constant union-find operations.

Step 1 / 9
Java
1List<Integer> numIslands2(int R, int C, int[][] positions) {
2    DSU d = new DSU(R * C); boolean[] land = new boolean[R * C];
3    List<Integer> out = new ArrayList<>(); int islands = 0;
4    for (int[] p : positions) {
5        int id = p[0] * C + p[1];
6        if (!land[id]) {                         // a repeated cell changes nothing
7            land[id] = true; islands++;
8            for (int[] dir : DIRS) {
9                int nr = p[0] + dir[0], nc = p[1] + dir[1];
10                if (nr >= 0 && nc >= 0 && nr < R && nc < C && land[nr * C + nc] && d.union(id, nr * C + nc)) islands--;   // merge neighbours
11            }
12        }
13        out.add(islands);
14    }
15    return out;
16}

Live state

0 islands

rows

3

cols

4

No condition evaluated on this step
Execution trace (dry run table)Show 9 steps
StepLineStateWhat happens
1L2rows=3 cols=4Every cell is its own set in a union-find over all R × C cells, but only land cells count. Adding land makes one new island; each adjacent land cell in a different set merges two islands and removes one. Each addition costs a few near-constant union-find operations.
2L7cell=0,0 merged=0 islands=1Add land at (0, 0): +1 island, and no neighbouring land to merge with. Now 1 island.
3L7cell=0,2 merged=0 islands=2Add land at (0, 2): +1 island, and no neighbouring land to merge with. Now 2 islands.
4L7cell=1,1 merged=0 islands=3Add land at (1, 1): +1 island, and no neighbouring land to merge with. Now 3 islands.
5L10cell=0,1 merged=3 islands=1Add land at (0, 1): +1 island, then 3 neighbouring islands merged with it (-3). Now 1 island.
6L7cell=2,3 merged=0 islands=2Add land at (2, 3): +1 island, and no neighbouring land to merge with. Now 2 islands.
7L10cell=1,3 merged=1 islands=2Add land at (1, 3): +1 island, then 1 neighbouring island merged with it (-1). Now 2 islands.
8L10cell=1,2 merged=2 islands=1Add land at (1, 2): +1 island, then 2 neighbouring islands merged with it (-2). Now 1 island.
9L15return=[1, 2, 3, 1, 2, 2, 1]Island counts after each addition: [1, 2, 3, 1, 2, 2, 1].

Practice ladder

Now try it yourself

Easy

  • Number of Provinces
  • Find if Path Exists in Graph

Medium

  • Redundant Connection
  • Accounts Merge
  • Number of Islands II

Advanced

  • Min Cost to Connect All Points
  • Redundant Connection II
  • Making A Large Island

Key takeaways

  • The return value of union tells you whether two groups merged: use it to count, to detect cycles and to select edges.
  • To group items that share a key, unite each item with the first item that had that key.
  • Kruskal = sort edges, keep an edge if union succeeds; islands = +1 for land, -1 for every successful neighbour union.