PK

PKBytes

Explore tracks
Chapter 31: Disjoint Set Union (Union-Find)
31.01Intermediate / Advanced6 topics14 min6 interactive animations

DSU model

A disjoint set union (union-find) keeps a collection of elements split into groups, and answers 'are these two in the same group?' and 'merge their groups' in nearly constant time.

Learning goals

  • Describe a partition of elements into equivalence classes
  • Implement find and union on a parent array
  • Count connected components and name each set's representative
  • Read a parent array as a forest and detect an invalid one

Prerequisites

ArraysTrees and parent pointersGraphs (basic vocabulary)

Friends of friends are friends: if A knows B and B knows C, they are all in one circle. Whenever you only need to merge circles and ask whether two people share one, a union-find does it without ever storing who knows whom.

31.01.1

Equivalence classes

A relation that is reflexive, symmetric and transitive is an **equivalence relation**, and it splits the elements into **equivalence classes**: every element belongs to exactly one class, and elements are related exactly when they share a class. 'Is connected to' in an undirected graph is such a relation, and so is 'has the same remainder modulo 5'. A union-find represents the classes directly.

The simplest representation, **quick-find**, stores a class label per element. Checking two elements is one comparison, but merging two classes relabels a whole class, O(n). Quick-find is the baseline that the tree representation of the next items improves: merging becomes cheap, and finding becomes a short walk.

Java
1class QuickFind {                                // each element stores its class label directly
2    private final int[] label;
3    QuickFind(int n) {
4        label = new int[n];
5        for (int i = 0; i < n; i++) label[i] = i;
6    }
7    boolean connected(int a, int b) { return label[a] == label[b]; }          // O(1)
8    void union(int a, int b) {                   // O(n): relabel a whole class
9        int from = label[a], to = label[b];
10        if (from == to) return;
11        for (int i = 0; i < label.length; i++) if (label[i] == from) label[i] = to;
12    }
13}

Union-find: find, union, path compression, union by size and rank

Interactive · edit the input

Your input

Try

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

0
1
2
3
4
5
Being followedParent just changedRoot foundAlready connectedA root (set representative)

parent[x]

00
11
22
33
44
55
Setup

6 elements, each in its own set: parent[x] = x makes every element a root (the set's representative). Union links one root under the other with no balancing.

Step 1 / 25
Java
1int[] parent, size, rank;                        // parent[x] == x for a root
2int findPlain(int x) { while (parent[x] != x) x = parent[x]; return x; }          // follow parents to the root
3int findCompress(int x) {                        // path compression: point everyone on the path at the root
4    if (parent[x] != x) parent[x] = findCompress(parent[x]);
5    return parent[x];
6}
7int findHalving(int x) {                         // path halving: skip one level as you climb
8    while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; }
9    return x;
10}
11boolean unionNaive(int a, int b) {               // link the first root under the second
12    int ra = find(a), rb = find(b);
13    if (ra == rb) return false;
14    parent[ra] = rb;
15    return true;
16}
17boolean unionBySize(int a, int b) {              // the smaller tree goes under the larger
18    int ra = find(a), rb = find(b);
19    if (ra == rb) return false;
20    if (size[ra] < size[rb]) { int t = ra; ra = rb; rb = t; }
21    parent[rb] = ra; size[ra] += size[rb];
22    return true;
23}
24boolean unionByRank(int a, int b) {              // the lower-rank root goes under the higher one
25    int ra = find(a), rb = find(b);
26    if (ra == rb) return false;
27    if (rank[ra] < rank[rb]) { int t = ra; ra = rb; rb = t; }
28    parent[rb] = ra;
29    if (rank[ra] == rank[rb]) rank[ra]++;
30    return true;
31}

Live state

0 find hops0 parent changes6 components

n

6

components

6

No condition evaluated on this step
Execution trace (dry run table)Show 25 steps
StepLineStateWhat happens
1L1n=6 components=66 elements, each in its own set: parent[x] = x makes every element a root (the set's representative). Union links one root under the other with no balancing.
2L2who=find(0) root=0find(0): 0 is its own parent: it is the root.
3L2who=find(1) root=1find(1): 1 is its own parent: it is the root.
4L14op=0-1 child=0 top=1 components=50-1: parent[0] = 1: the root of the first element goes under the root of the second. 5 sets left.
5L2who=find(1) root=1find(1): 1 is its own parent: it is the root.
6L2who=find(2) root=2find(2): 2 is its own parent: it is the root.
7L14op=1-2 child=1 top=2 components=41-2: parent[1] = 2: the root of the first element goes under the root of the second. 4 sets left.
8L2who=find(2) root=2find(2): 2 is its own parent: it is the root.
9L2who=find(3) root=3find(3): 3 is its own parent: it is the root.
10L14op=2-3 child=2 top=3 components=32-3: parent[2] = 3: the root of the first element goes under the root of the second. 3 sets left.
11L2who=find(3) root=3find(3): 3 is its own parent: it is the root.
12L2who=find(4) root=4find(4): 4 is its own parent: it is the root.
13L14op=3-4 child=3 top=4 components=23-4: parent[3] = 4: the root of the first element goes under the root of the second. 2 sets left.
14L2who=find(4) root=4find(4): 4 is its own parent: it is the root.
15L2who=find(5) root=5find(5): 5 is its own parent: it is the root.
16L14op=4-5 child=4 top=5 components=14-5: parent[4] = 5: the root of the first element goes under the root of the second. 1 set left.
17L2who=find(0) from=0 to=1 hops=1find(0): 0 is not a root, follow parent[0] = 1.
18L2who=find(0) from=1 to=2 hops=2find(0): 1 is not a root, follow parent[1] = 2.
19L2who=find(0) from=2 to=3 hops=3find(0): 2 is not a root, follow parent[2] = 3.
20L2who=find(0) from=3 to=4 hops=4find(0): 3 is not a root, follow parent[3] = 4.
21L2who=find(0) from=4 to=5 hops=5find(0): 4 is not a root, follow parent[4] = 5.
22L2who=find(0) root=5 depth=5find(0): the root is 5, 5 steps up.
23L2who=find(5) root=5find(5): 5 is its own parent: it is the root.
24L1op=0?5 root of a=5 root of b=5 connected=true0?5: the roots are 5 and 5, so 0 and 5 are connected.
25L1return=1 tallest tree=5 find hops=5 parent changes=01 set remains. The tallest tree has height 5, and all the finds together followed 5 parent links.
31.01.2

Find

The tree representation stores a parent array: parent[x] is the parent of x, and a **root** is its own parent. find(x) follows parents until it reaches a root, and returns it: two elements are in the same set exactly when their roots are equal. The cost is the depth of x, which the optimisations of the next lesson keep tiny.

Open the animation with the preset "Chain, naive linking: a tall tree": every hop of find is shown as a step from a node to its parent. A find on the deepest node of a chain of 6 follows 5 parent links, which is why unbalanced trees are slow.

Java
1class Dsu {
2    final int[] parent;
3    Dsu(int n) {
4        parent = new int[n];
5        for (int i = 0; i < n; i++) parent[i] = i;      // every element is its own root
6    }
7    int find(int x) {
8        while (parent[x] != x) x = parent[x];           // follow parents to the root
9        return x;
10    }
11}

Union-find: find, union, path compression, union by size and rank

Interactive · edit the input

Your input

Try

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

0
1
2
3
4
5
Being followedParent just changedRoot foundAlready connectedA root (set representative)

parent[x]

00
11
22
33
44
55
Setup

6 elements, each in its own set: parent[x] = x makes every element a root (the set's representative). Union links one root under the other with no balancing.

Step 1 / 25
Java
1int[] parent, size, rank;                        // parent[x] == x for a root
2int findPlain(int x) { while (parent[x] != x) x = parent[x]; return x; }          // follow parents to the root
3int findCompress(int x) {                        // path compression: point everyone on the path at the root
4    if (parent[x] != x) parent[x] = findCompress(parent[x]);
5    return parent[x];
6}
7int findHalving(int x) {                         // path halving: skip one level as you climb
8    while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; }
9    return x;
10}
11boolean unionNaive(int a, int b) {               // link the first root under the second
12    int ra = find(a), rb = find(b);
13    if (ra == rb) return false;
14    parent[ra] = rb;
15    return true;
16}
17boolean unionBySize(int a, int b) {              // the smaller tree goes under the larger
18    int ra = find(a), rb = find(b);
19    if (ra == rb) return false;
20    if (size[ra] < size[rb]) { int t = ra; ra = rb; rb = t; }
21    parent[rb] = ra; size[ra] += size[rb];
22    return true;
23}
24boolean unionByRank(int a, int b) {              // the lower-rank root goes under the higher one
25    int ra = find(a), rb = find(b);
26    if (ra == rb) return false;
27    if (rank[ra] < rank[rb]) { int t = ra; ra = rb; rb = t; }
28    parent[rb] = ra;
29    if (rank[ra] == rank[rb]) rank[ra]++;
30    return true;
31}

Live state

0 find hops0 parent changes6 components

n

6

components

6

No condition evaluated on this step
Execution trace (dry run table)Show 25 steps
StepLineStateWhat happens
1L1n=6 components=66 elements, each in its own set: parent[x] = x makes every element a root (the set's representative). Union links one root under the other with no balancing.
2L2who=find(0) root=0find(0): 0 is its own parent: it is the root.
3L2who=find(1) root=1find(1): 1 is its own parent: it is the root.
4L14op=0-1 child=0 top=1 components=50-1: parent[0] = 1: the root of the first element goes under the root of the second. 5 sets left.
5L2who=find(1) root=1find(1): 1 is its own parent: it is the root.
6L2who=find(2) root=2find(2): 2 is its own parent: it is the root.
7L14op=1-2 child=1 top=2 components=41-2: parent[1] = 2: the root of the first element goes under the root of the second. 4 sets left.
8L2who=find(2) root=2find(2): 2 is its own parent: it is the root.
9L2who=find(3) root=3find(3): 3 is its own parent: it is the root.
10L14op=2-3 child=2 top=3 components=32-3: parent[2] = 3: the root of the first element goes under the root of the second. 3 sets left.
11L2who=find(3) root=3find(3): 3 is its own parent: it is the root.
12L2who=find(4) root=4find(4): 4 is its own parent: it is the root.
13L14op=3-4 child=3 top=4 components=23-4: parent[3] = 4: the root of the first element goes under the root of the second. 2 sets left.
14L2who=find(4) root=4find(4): 4 is its own parent: it is the root.
15L2who=find(5) root=5find(5): 5 is its own parent: it is the root.
16L14op=4-5 child=4 top=5 components=14-5: parent[4] = 5: the root of the first element goes under the root of the second. 1 set left.
17L2who=find(0) from=0 to=1 hops=1find(0): 0 is not a root, follow parent[0] = 1.
18L2who=find(0) from=1 to=2 hops=2find(0): 1 is not a root, follow parent[1] = 2.
19L2who=find(0) from=2 to=3 hops=3find(0): 2 is not a root, follow parent[2] = 3.
20L2who=find(0) from=3 to=4 hops=4find(0): 3 is not a root, follow parent[3] = 4.
21L2who=find(0) from=4 to=5 hops=5find(0): 4 is not a root, follow parent[4] = 5.
22L2who=find(0) root=5 depth=5find(0): the root is 5, 5 steps up.
23L2who=find(5) root=5find(5): 5 is its own parent: it is the root.
24L1op=0?5 root of a=5 root of b=5 connected=true0?5: the roots are 5 and 5, so 0 and 5 are connected.
25L1return=1 tallest tree=5 find hops=5 parent changes=01 set remains. The tallest tree has height 5, and all the finds together followed 5 parent links.
31.01.3

Union

union(a, b) merges the sets of a and b: find both roots, and if they differ, make one root the parent of the other. Nothing else changes: no element moves, and one pointer is enough to merge two whole sets. The method returns whether a merge happened, which is exactly the information many problems need (for example 'did this edge connect two components?').

The naive rule below hangs the first root under the second. It is correct but can build a chain, as the preset "Chain, naive linking: a tall tree" shows for 0-1 1-2 2-3 3-4 4-5: the tree ends up with height 5. Choosing which root goes on top, by size or rank, fixes that.

Java
1class Dsu {
2    final int[] parent;
3    Dsu(int n) {
4        parent = new int[n];
5        for (int i = 0; i < n; i++) parent[i] = i;
6    }
7    int find(int x) {
8        while (parent[x] != x) x = parent[x];
9        return x;
10    }
11    boolean union(int a, int b) {                // link the first root under the second
12        int ra = find(a), rb = find(b);
13        if (ra == rb) return false;              // already in the same set
14        parent[ra] = rb;
15        return true;
16    }
17}

Union-find: find, union, path compression, union by size and rank

Interactive · edit the input

Your input

Try

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

0
1
2
3
4
5
Being followedParent just changedRoot foundAlready connectedA root (set representative)

parent[x]

00
11
22
33
44
55
Setup

6 elements, each in its own set: parent[x] = x makes every element a root (the set's representative). Union links one root under the other with no balancing.

Step 1 / 25
Java
1int[] parent, size, rank;                        // parent[x] == x for a root
2int findPlain(int x) { while (parent[x] != x) x = parent[x]; return x; }          // follow parents to the root
3int findCompress(int x) {                        // path compression: point everyone on the path at the root
4    if (parent[x] != x) parent[x] = findCompress(parent[x]);
5    return parent[x];
6}
7int findHalving(int x) {                         // path halving: skip one level as you climb
8    while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; }
9    return x;
10}
11boolean unionNaive(int a, int b) {               // link the first root under the second
12    int ra = find(a), rb = find(b);
13    if (ra == rb) return false;
14    parent[ra] = rb;
15    return true;
16}
17boolean unionBySize(int a, int b) {              // the smaller tree goes under the larger
18    int ra = find(a), rb = find(b);
19    if (ra == rb) return false;
20    if (size[ra] < size[rb]) { int t = ra; ra = rb; rb = t; }
21    parent[rb] = ra; size[ra] += size[rb];
22    return true;
23}
24boolean unionByRank(int a, int b) {              // the lower-rank root goes under the higher one
25    int ra = find(a), rb = find(b);
26    if (ra == rb) return false;
27    if (rank[ra] < rank[rb]) { int t = ra; ra = rb; rb = t; }
28    parent[rb] = ra;
29    if (rank[ra] == rank[rb]) rank[ra]++;
30    return true;
31}

Live state

0 find hops0 parent changes6 components

n

6

components

6

No condition evaluated on this step
Execution trace (dry run table)Show 25 steps
StepLineStateWhat happens
1L1n=6 components=66 elements, each in its own set: parent[x] = x makes every element a root (the set's representative). Union links one root under the other with no balancing.
2L2who=find(0) root=0find(0): 0 is its own parent: it is the root.
3L2who=find(1) root=1find(1): 1 is its own parent: it is the root.
4L14op=0-1 child=0 top=1 components=50-1: parent[0] = 1: the root of the first element goes under the root of the second. 5 sets left.
5L2who=find(1) root=1find(1): 1 is its own parent: it is the root.
6L2who=find(2) root=2find(2): 2 is its own parent: it is the root.
7L14op=1-2 child=1 top=2 components=41-2: parent[1] = 2: the root of the first element goes under the root of the second. 4 sets left.
8L2who=find(2) root=2find(2): 2 is its own parent: it is the root.
9L2who=find(3) root=3find(3): 3 is its own parent: it is the root.
10L14op=2-3 child=2 top=3 components=32-3: parent[2] = 3: the root of the first element goes under the root of the second. 3 sets left.
11L2who=find(3) root=3find(3): 3 is its own parent: it is the root.
12L2who=find(4) root=4find(4): 4 is its own parent: it is the root.
13L14op=3-4 child=3 top=4 components=23-4: parent[3] = 4: the root of the first element goes under the root of the second. 2 sets left.
14L2who=find(4) root=4find(4): 4 is its own parent: it is the root.
15L2who=find(5) root=5find(5): 5 is its own parent: it is the root.
16L14op=4-5 child=4 top=5 components=14-5: parent[4] = 5: the root of the first element goes under the root of the second. 1 set left.
17L2who=find(0) from=0 to=1 hops=1find(0): 0 is not a root, follow parent[0] = 1.
18L2who=find(0) from=1 to=2 hops=2find(0): 1 is not a root, follow parent[1] = 2.
19L2who=find(0) from=2 to=3 hops=3find(0): 2 is not a root, follow parent[2] = 3.
20L2who=find(0) from=3 to=4 hops=4find(0): 3 is not a root, follow parent[3] = 4.
21L2who=find(0) from=4 to=5 hops=5find(0): 4 is not a root, follow parent[4] = 5.
22L2who=find(0) root=5 depth=5find(0): the root is 5, 5 steps up.
23L2who=find(5) root=5find(5): 5 is its own parent: it is the root.
24L1op=0?5 root of a=5 root of b=5 connected=true0?5: the roots are 5 and 5, so 0 and 5 are connected.
25L1return=1 tallest tree=5 find hops=5 parent changes=01 set remains. The tallest tree has height 5, and all the finds together followed 5 parent links.
31.01.4

Connected components

Start with n sets, one per vertex, and process the edges of an undirected graph: every edge that joins two different sets is a merge and lowers the number of components by one. After all edges, the count is the number of connected components. It takes O(E) union-find operations and no adjacency lists.

This is the advantage over a search: edges can arrive one at a time and the count is always current. In the animation's "Provinces: count components" preset, 6 vertices and the edges 0-1 1-2 3-4 2-0 4-5 give 2 components; the edge 2-0 is skipped because 0 and 2 are already connected.

Java
1static int countComponents(int n, int[][] edges) {
2    int[] parent = new int[n];
3    for (int i = 0; i < n; i++) parent[i] = i;
4    int components = n;
5    for (int[] e : edges) {
6        int a = e[0], b = e[1];
7        while (parent[a] != a) a = parent[a];
8        while (parent[b] != b) b = parent[b];
9        if (a != b) { parent[a] = b; components--; }       // a merge: one component fewer
10    }
11    return components;
12}

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.01.5

Representative

Each set is named by its **representative**, the root of its tree. The name is not meaningful by itself and can change when sets merge, but it is consistent at any moment: all members of a set return the same root. That is enough to group elements, to key a map by set, or to label components.

To list the groups, call find for every element and bucket by the root. The code below returns the representative of every element and the groups in order of their smallest member. Never cache a representative across a union: the old root may have lost its status.

Java
1class Dsu {
2    final int[] parent;
3    Dsu(int n) {
4        parent = new int[n];
5        for (int i = 0; i < n; i++) parent[i] = i;
6    }
7    int find(int x) {
8        while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; }
9        return x;
10    }
11    void union(int a, int b) { parent[find(a)] = find(b); }
12    int[] representatives() {                    // the root of every element
13        int[] rep = new int[parent.length];
14        for (int i = 0; i < rep.length; i++) rep[i] = find(i);
15        return rep;
16    }
17    Map<Integer, List<Integer>> groups() {       // root -> members in increasing order
18        Map<Integer, List<Integer>> g = new TreeMap<>();
19        for (int i = 0; i < parent.length; i++) g.computeIfAbsent(find(i), k -> new ArrayList<>()).add(i);
20        return g;
21    }
22}

Union-find: find, union, path compression, union by size and rank

Interactive · edit the input

Your input

Try

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

0
1
2
3
4
5
Being followedParent just changedRoot foundAlready connectedA root (set representative)

parent[x]

00
11
22
33
44
55
Setup

6 elements, each in its own set: parent[x] = x makes every element a root (the set's representative). Union links one root under the other with no balancing.

Step 1 / 25
Java
1int[] parent, size, rank;                        // parent[x] == x for a root
2int findPlain(int x) { while (parent[x] != x) x = parent[x]; return x; }          // follow parents to the root
3int findCompress(int x) {                        // path compression: point everyone on the path at the root
4    if (parent[x] != x) parent[x] = findCompress(parent[x]);
5    return parent[x];
6}
7int findHalving(int x) {                         // path halving: skip one level as you climb
8    while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; }
9    return x;
10}
11boolean unionNaive(int a, int b) {               // link the first root under the second
12    int ra = find(a), rb = find(b);
13    if (ra == rb) return false;
14    parent[ra] = rb;
15    return true;
16}
17boolean unionBySize(int a, int b) {              // the smaller tree goes under the larger
18    int ra = find(a), rb = find(b);
19    if (ra == rb) return false;
20    if (size[ra] < size[rb]) { int t = ra; ra = rb; rb = t; }
21    parent[rb] = ra; size[ra] += size[rb];
22    return true;
23}
24boolean unionByRank(int a, int b) {              // the lower-rank root goes under the higher one
25    int ra = find(a), rb = find(b);
26    if (ra == rb) return false;
27    if (rank[ra] < rank[rb]) { int t = ra; ra = rb; rb = t; }
28    parent[rb] = ra;
29    if (rank[ra] == rank[rb]) rank[ra]++;
30    return true;
31}

Live state

0 find hops0 parent changes6 components

n

6

components

6

No condition evaluated on this step
Execution trace (dry run table)Show 25 steps
StepLineStateWhat happens
1L1n=6 components=66 elements, each in its own set: parent[x] = x makes every element a root (the set's representative). Union links one root under the other with no balancing.
2L2who=find(0) root=0find(0): 0 is its own parent: it is the root.
3L2who=find(1) root=1find(1): 1 is its own parent: it is the root.
4L14op=0-1 child=0 top=1 components=50-1: parent[0] = 1: the root of the first element goes under the root of the second. 5 sets left.
5L2who=find(1) root=1find(1): 1 is its own parent: it is the root.
6L2who=find(2) root=2find(2): 2 is its own parent: it is the root.
7L14op=1-2 child=1 top=2 components=41-2: parent[1] = 2: the root of the first element goes under the root of the second. 4 sets left.
8L2who=find(2) root=2find(2): 2 is its own parent: it is the root.
9L2who=find(3) root=3find(3): 3 is its own parent: it is the root.
10L14op=2-3 child=2 top=3 components=32-3: parent[2] = 3: the root of the first element goes under the root of the second. 3 sets left.
11L2who=find(3) root=3find(3): 3 is its own parent: it is the root.
12L2who=find(4) root=4find(4): 4 is its own parent: it is the root.
13L14op=3-4 child=3 top=4 components=23-4: parent[3] = 4: the root of the first element goes under the root of the second. 2 sets left.
14L2who=find(4) root=4find(4): 4 is its own parent: it is the root.
15L2who=find(5) root=5find(5): 5 is its own parent: it is the root.
16L14op=4-5 child=4 top=5 components=14-5: parent[4] = 5: the root of the first element goes under the root of the second. 1 set left.
17L2who=find(0) from=0 to=1 hops=1find(0): 0 is not a root, follow parent[0] = 1.
18L2who=find(0) from=1 to=2 hops=2find(0): 1 is not a root, follow parent[1] = 2.
19L2who=find(0) from=2 to=3 hops=3find(0): 2 is not a root, follow parent[2] = 3.
20L2who=find(0) from=3 to=4 hops=4find(0): 3 is not a root, follow parent[3] = 4.
21L2who=find(0) from=4 to=5 hops=5find(0): 4 is not a root, follow parent[4] = 5.
22L2who=find(0) root=5 depth=5find(0): the root is 5, 5 steps up.
23L2who=find(5) root=5find(5): 5 is its own parent: it is the root.
24L1op=0?5 root of a=5 root of b=5 connected=true0?5: the roots are 5 and 5, so 0 and 5 are connected.
25L1return=1 tallest tree=5 find hops=5 parent changes=01 set remains. The tallest tree has height 5, and all the finds together followed 5 parent links.
31.01.6

Parent arrays

The whole structure is one integer array. parent[x] == x marks a root; any other entry is an edge to a parent, so the array describes a **forest** of rooted trees, one per set. A valid parent array has no cycle other than the self-loops of the roots: following parents from any element must reach a root. The animation draws the forest with the array shown above it, so you can read the two views side by side.

To work with a parent array directly, two helpers are useful: the depth of an element (number of parent links to its root) and a validity check that rejects cycles. The check runs in O(n) by colouring: an element is 'in progress' while its path is explored and 'done' once it is known to reach a root.

Java
1static int depth(int[] parent, int x) {          // number of parent links from x to its root
2    int d = 0;
3    while (parent[x] != x) { x = parent[x]; d++; }
4    return d;
5}
6static boolean isForest(int[] parent) {          // every element must reach a root without cycling
7    int n = parent.length;
8    int[] state = new int[n];                    // 0 unvisited, 1 on the current path, 2 known good
9    for (int s = 0; s < n; s++) {
10        int x = s;
11        while (state[x] == 0 && parent[x] != x) { state[x] = 1; x = parent[x]; }
12        if (state[x] == 1) return false;         // we came back to the current path: a cycle
13        for (int y = s; state[y] == 1; y = parent[y]) state[y] = 2;
14        state[x] = 2;
15    }
16    return true;
17}

Union-find: find, union, path compression, union by size and rank

Interactive · edit the input

Your input

Try

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

0
1
2
3
4
5
Being followedParent just changedRoot foundAlready connectedA root (set representative)

parent[x]

00
11
22
33
44
55
Setup

6 elements, each in its own set: parent[x] = x makes every element a root (the set's representative). Union links one root under the other with no balancing.

Step 1 / 25
Java
1int[] parent, size, rank;                        // parent[x] == x for a root
2int findPlain(int x) { while (parent[x] != x) x = parent[x]; return x; }          // follow parents to the root
3int findCompress(int x) {                        // path compression: point everyone on the path at the root
4    if (parent[x] != x) parent[x] = findCompress(parent[x]);
5    return parent[x];
6}
7int findHalving(int x) {                         // path halving: skip one level as you climb
8    while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; }
9    return x;
10}
11boolean unionNaive(int a, int b) {               // link the first root under the second
12    int ra = find(a), rb = find(b);
13    if (ra == rb) return false;
14    parent[ra] = rb;
15    return true;
16}
17boolean unionBySize(int a, int b) {              // the smaller tree goes under the larger
18    int ra = find(a), rb = find(b);
19    if (ra == rb) return false;
20    if (size[ra] < size[rb]) { int t = ra; ra = rb; rb = t; }
21    parent[rb] = ra; size[ra] += size[rb];
22    return true;
23}
24boolean unionByRank(int a, int b) {              // the lower-rank root goes under the higher one
25    int ra = find(a), rb = find(b);
26    if (ra == rb) return false;
27    if (rank[ra] < rank[rb]) { int t = ra; ra = rb; rb = t; }
28    parent[rb] = ra;
29    if (rank[ra] == rank[rb]) rank[ra]++;
30    return true;
31}

Live state

0 find hops0 parent changes6 components

n

6

components

6

No condition evaluated on this step
Execution trace (dry run table)Show 25 steps
StepLineStateWhat happens
1L1n=6 components=66 elements, each in its own set: parent[x] = x makes every element a root (the set's representative). Union links one root under the other with no balancing.
2L2who=find(0) root=0find(0): 0 is its own parent: it is the root.
3L2who=find(1) root=1find(1): 1 is its own parent: it is the root.
4L14op=0-1 child=0 top=1 components=50-1: parent[0] = 1: the root of the first element goes under the root of the second. 5 sets left.
5L2who=find(1) root=1find(1): 1 is its own parent: it is the root.
6L2who=find(2) root=2find(2): 2 is its own parent: it is the root.
7L14op=1-2 child=1 top=2 components=41-2: parent[1] = 2: the root of the first element goes under the root of the second. 4 sets left.
8L2who=find(2) root=2find(2): 2 is its own parent: it is the root.
9L2who=find(3) root=3find(3): 3 is its own parent: it is the root.
10L14op=2-3 child=2 top=3 components=32-3: parent[2] = 3: the root of the first element goes under the root of the second. 3 sets left.
11L2who=find(3) root=3find(3): 3 is its own parent: it is the root.
12L2who=find(4) root=4find(4): 4 is its own parent: it is the root.
13L14op=3-4 child=3 top=4 components=23-4: parent[3] = 4: the root of the first element goes under the root of the second. 2 sets left.
14L2who=find(4) root=4find(4): 4 is its own parent: it is the root.
15L2who=find(5) root=5find(5): 5 is its own parent: it is the root.
16L14op=4-5 child=4 top=5 components=14-5: parent[4] = 5: the root of the first element goes under the root of the second. 1 set left.
17L2who=find(0) from=0 to=1 hops=1find(0): 0 is not a root, follow parent[0] = 1.
18L2who=find(0) from=1 to=2 hops=2find(0): 1 is not a root, follow parent[1] = 2.
19L2who=find(0) from=2 to=3 hops=3find(0): 2 is not a root, follow parent[2] = 3.
20L2who=find(0) from=3 to=4 hops=4find(0): 3 is not a root, follow parent[3] = 4.
21L2who=find(0) from=4 to=5 hops=5find(0): 4 is not a root, follow parent[4] = 5.
22L2who=find(0) root=5 depth=5find(0): the root is 5, 5 steps up.
23L2who=find(5) root=5find(5): 5 is its own parent: it is the root.
24L1op=0?5 root of a=5 root of b=5 connected=true0?5: the roots are 5 and 5, so 0 and 5 are connected.
25L1return=1 tallest tree=5 find hops=5 parent changes=01 set remains. The tallest tree has height 5, and all the finds together followed 5 parent links.

Practice ladder

Now try it yourself

Easy

  • Find if Path Exists in Graph
  • Find the Town Judge

Medium

  • Number of Provinces
  • Number of Connected Components in an Undirected Graph

Advanced

  • Smallest String With Swaps
  • Satisfiability of Equality Equations

Key takeaways

  • A union-find stores a partition: a parent array whose roots are the set representatives.
  • find walks to the root; union links two roots and reports whether anything changed.
  • Counting components = n minus the number of successful unions.