PK

PKBytes

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

Optimizations

Path compression, path halving, union by size and union by rank keep the trees nearly flat, so a sequence of operations costs almost constant time per operation.

Learning goals

  • Flatten the path walked by find with compression or halving
  • Keep trees shallow by linking the smaller tree under the larger
  • Compare union by size and union by rank
  • State the amortised bound with the inverse Ackermann function

Prerequisites

DSU modelAmortised analysis (informal)

In a company with a deep management chain, every report takes many hops to reach the CEO. Reorganise whenever someone is asked: connect everyone you passed straight to the top, and next time the walk is one step.

31.02.1

Path compression

**Path compression** makes every node visited by find a direct child of the root. The recursive version does it in one line: parent[x] = find(parent[x]). The tree gets flatter every time you search it, and the cost of the walk is paid back by all the later finds that are now one step.

Run the preset "Chain, then one find compresses it" (0-1 1-2 2-3 3-4 4-5 0?5 with compression): the unions build a chain and the final find(0) follows 5 links, then re-points 0, 1, 2 and 3 straight at the root. For an 8-element chain with the query 0?7 twice, plain linking ends with a tree of height 7 and the finds follow 14 links, but compression follows 8 and re-points 6 nodes, leaving height 1.

Java
1class DsuCompress {
2    final int[] parent;
3    DsuCompress(int n) {
4        parent = new int[n];
5        for (int i = 0; i < n; i++) parent[i] = i;
6    }
7    int find(int x) {                            // path compression: point everyone on the path at the root
8        if (parent[x] != x) parent[x] = find(parent[x]);
9        return parent[x];
10    }
11    boolean union(int a, int b) {
12        int ra = find(a), rb = find(b);
13        if (ra == rb) return false;
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.02.2

Path halving

**Path halving** compresses while climbing, in a single pass and without recursion: at each step set parent[x] = parent[parent[x]] and move to the new parent. Every node on the path ends up pointing at its grandparent, so the path length is halved. It needs no stack, which avoids deep recursion on long chains, and gives the same asymptotic bound as full compression.

In the preset "Rank + path halving" (8 elements) the animation prints each halving step as 'parent[x] = parent[parent[x]]' and notes when no change was needed because the node already pointed at the root. All the finds together follow 3 parent links, and the tallest tree has height 2.

Java
1class DsuHalving {
2    final int[] parent;
3    DsuHalving(int n) {
4        parent = new int[n];
5        for (int i = 0; i < n; i++) parent[i] = i;
6    }
7    int find(int x) {                            // path halving: skip one level as you climb
8        while (parent[x] != x) {
9            parent[x] = parent[parent[x]];
10            x = parent[x];
11        }
12        return x;
13    }
14    boolean union(int a, int b) {
15        int ra = find(a), rb = find(b);
16        if (ra == rb) return false;
17        parent[ra] = rb;
18        return true;
19    }
20}

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

Union by size

**Union by size** keeps a size per root and always hangs the smaller tree under the larger. A node's depth grows by one only when its tree is merged under a tree at least as big, so its set at least doubles each time its depth increases. Hence no depth exceeds log2 n, even without path compression.

Compare "Chain, naive linking: a tall tree" with "Same chain, union by size" in the animation: the same operations 0-1 1-2 2-3 3-4 4-5 0?5 give a tree of height 5 with naive linking and a tree of height 1 with union by size, because each new singleton is hung under the big tree instead of the other way round.

Java
1class DsuBySize {
2    final int[] parent, size;
3    DsuBySize(int n) {
4        parent = new int[n]; size = new int[n];
5        for (int i = 0; i < n; i++) { parent[i] = i; size[i] = 1; }
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) {
12        int ra = find(a), rb = find(b);
13        if (ra == rb) return false;
14        if (size[ra] < size[rb]) { int t = ra; ra = rb; rb = t; }    // ra is the larger tree
15        parent[rb] = ra;
16        size[ra] += size[rb];
17        return true;
18    }
19}

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

Union by rank

**Union by rank** keeps an upper bound on the height of each tree instead of its exact size. A single node has rank 0. When two roots of different rank are merged, the lower-rank root goes under the higher and no rank changes; when the ranks are equal, one root goes under the other and the new root's rank increases by 1. A tree of rank r has at least 2^r nodes, so ranks never exceed log2 n.

Rank is cheaper to maintain than size when path compression is also used, because compression makes heights shrink without updating any rank: ranks stay valid as upper bounds, not exact heights. The preset "Rank + path halving" uses both: watch the 'rank' labels under the roots grow only when two equal ranks meet.

Java
1class DsuByRank {
2    final int[] parent, rank;
3    DsuByRank(int n) {
4        parent = new int[n]; rank = 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) {
12        int ra = find(a), rb = find(b);
13        if (ra == rb) return false;
14        if (rank[ra] < rank[rb]) { int t = ra; ra = rb; rb = t; }    // ra has the higher rank
15        parent[rb] = ra;
16        if (rank[ra] == rank[rb]) rank[ra]++;    // equal ranks: the new root is one taller
17        return true;
18    }
19}

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

Inverse Ackermann amortization

With union by size or rank **and** path compression or halving, a sequence of m operations on n elements takes O(m α(n)) time, where α is the inverse Ackermann function. This is a theorem of Tarjan (1975) and it is optimal for the problem under common models; this course quotes it without proof. α(n) grows so slowly that it is at most 4 for any n that can be written down in the universe, so each operation is constant time for all practical purposes.

You can see the effect without the theory. The function below runs 2n random unions and counts the parent links followed per find. Measured with seed 7 it gives about 0.73 links per find for n = 1,000, for n = 100,000 and for n = 1,000,000: the average does not grow with n at all. Either optimisation alone gives O(log n) amortised; together they give the near-constant bound.

TechniqueTime for m operations (amortised)
Plain linking, no optimisationO(n) per find in the worst case
Union by size or rank onlyO(log n) per operation
Path compression onlyO(log n) per operation, amortised
BothO(α(n)) per operation, α(n) ≤ 4 in practice
Java
1static double averageHops(int n, long seed) {    // parent links followed per find, size + path halving
2    int[] parent = new int[n], size = new int[n];
3    for (int i = 0; i < n; i++) { parent[i] = i; size[i] = 1; }
4    Random rnd = new Random(seed);
5    long hops = 0, finds = 0;
6    for (int op = 0; op < 2 * n; op++) {
7        int[] roots = new int[2];
8        for (int k = 0; k < 2; k++) {
9            int x = rnd.nextInt(n);
10            while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; hops++; }
11            roots[k] = x;
12            finds++;
13        }
14        if (roots[0] != roots[1]) {
15            if (size[roots[0]] < size[roots[1]]) { int t = roots[0]; roots[0] = roots[1]; roots[1] = t; }
16            parent[roots[1]] = roots[0];
17            size[roots[0]] += size[roots[1]];
18        }
19    }
20    return (double) hops / finds;
21}

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

Medium

  • Redundant Connection
  • Most Stones Removed with Same Row or Column

Advanced

  • Swim in Rising Water
  • Optimize Water Distribution in a Village

Key takeaways

  • Path compression or halving flattens the tree during find; union by size or rank keeps trees shallow during union.
  • Either alone gives O(log n) amortised; both together give O(α(n)), effectively constant.
  • Ranks stay valid as height bounds even when compression changes the real heights.