Disjoint Set Union· 20 min

Union-Find

Near-O(1) set merging with union by rank and path compression

Step 1 / 37

Current step

1 / 37

Start with 8 elements, each its own parent — 8 separate sets.

Step log

Being unioned
Root
Find path (compressing)
union_find.java
1import java.util.Arrays;
2 
3public class Main {
4    private final int[] parent;
5    private final int[] rank;
6 
7    public Main(int size) {
8        parent = new int[size];
9        rank = new int[size];
10        for (int i = 0; i < size; i++) parent[i] = i;
11    }
12 
13    public int find(int value) {
14        if (parent[value] != value) parent[value] = find(parent[value]);
15        return parent[value];
16    }
17 
18    public void union(int first, int second) {
19        int rootA = find(first), rootB = find(second);
20        if (rootA == rootB) return;
21        if (rank[rootA] < rank[rootB]) parent[rootA] = rootB;
22        else if (rank[rootA] > rank[rootB]) parent[rootB] = rootA;
23        else { parent[rootB] = rootA; rank[rootA]++; }
24    }
25 
26}
● Java
find / union
O(α(n)) ≈ O(1)
Operation
init
Sets remaining
8
Elements
8
parent[0]
0
parent[1]
1
parent[2]
2
parent[3]
3
parent[4]
4
parent[5]
5
parent[6]
6
parent[7]
7
42 / 46