LESSON 55 · ADVANCED4 min read

Disjoint Set Union (DSU) with Path Compression and Kruskal's Minimum Spanning Tree

Master Disjoint Set Union (Union-Find) with path compression and union-by-rank, applying it to cycle detection and Kruskal's Minimum Spanning Tree algorithm.

OpenJDK 21+ (LTS)Free to readModule 14 of 15

YOUR NEXT SMALL WINS

By the end, you’ll be able to…

Implement Disjoint Set Union (DSU) with path compression and union-by-rank to achieve near-constant alpha(n) operations
Prove why the Inverse Ackermann function alpha(n) remains < 5 for all practical universe sizes
Construct Kruskal's Minimum Spanning Tree (MST) algorithm to design optimal low-cost network topologies

01The Disjoint Set Union (DSU) Abstraction

Disjoint Set Union (also known as Union-Find) maintains a partition of n elements into disjoint (non-overlapping) dynamic sets. Each set is identified by a representative element called its root.

DSU supports two core operations: 1. find(x): Returns the representative root of the set containing element x. 2. union(x, y): Merges the set containing x with the set containing y.

A naive tree-based implementation can degrade into a linear chain if elements are united in sequential order, causing find(x) to take O(n) worst-case time. By adding two optimizations—Union by Rank and Path Compression—the amortized time per operation drops to O(alpha(n)), where alpha is the Inverse Ackermann function.

example.js☕Java

Ctrl + ↵

public class DisjointSetUnion {
    private final int[] parent;
    private final int[] rank;
    private int componentCount;

public DisjointSetUnion(int n) {
        this.parent = new int[n];
        this.rank = new int[n];
        this.componentCount = n;
        for (int i = 0; i < n; i++) {
            parent[i] = i; // Each node is its own representative initially
            rank[i] = 0;
        }
    }

// Find with Path Compression: flattens the tree directly to the root
    public int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]); // Path compression
        }
        return parent[x];
    }

// Union by Rank: attaches smaller tree beneath the root of the larger tree
    public boolean union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);

if (rootX == rootY) {
            return false; // Already in the same set: cycle detected!
        }

if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
        } else {
            parent[rootY] = rootX;
            rank[rootX]++;
        }

componentCount--;
        return true;
    }

public int getComponentCount() { return componentCount; }
}

Output

Click Run or press Ctrl+Enter

Output will appear here after you run the code.

02The Near-Constant Magic of the Inverse Ackermann Function

The Ackermann function A(m, n) is one of the fastest-growing functions in mathematics. A(4, 2) is 2^65536—a number vastly greater than the estimated number of atoms in the entire observable universe (~10^80).

The Inverse Ackermann function, alpha(n), represents the inverse: the value of m such that A(m, m) >= n. For any input size n that could ever be processed by any computer system (n <= 10^80), alpha(n) <= 4.

Consequently, an amortized runtime of O(alpha(n)) per operation is practically indistinguishable from strict O(1) constant time, making DSU one of the most efficient data structures known in computer science.

03Kruskal's Algorithm for Minimum Spanning Trees (MST)

A Minimum Spanning Tree (MST) of a connected, undirected graph with weighted edges is a subset of edges that connects all vertices together without cycles, minimizing the total edge weight.

Kruskal's algorithm finds the MST using a greedy strategy: 1. Sort all edges in ascending order of weight. 2. Initialize a DSU where each vertex is an independent component.

3. Iterate through sorted edges: For edge (u, v) with weight w: If find(u) != find(v), add this edge to the MST and call union(u, v). If find(u) == find(v), discard the edge because adding it would form a cycle. 4. Stop when (V - 1) edges have been added.

example.js☕Java

Ctrl + ↵

Output

Click Run or press Ctrl+Enter

Output will appear here after you run the code.

04Kruskal vs Prim MST Comparison

Both Kruskal's and Prim's algorithms find an MST, but they excel in different graph densities:

For sparse graphs (E ~ V) like road networks and fiber optic grids, Kruskal's algorithm with DSU is standard and easy to implement.

notes.txtPlain text

+--------------------+---------------------+----------------------+---------------------+| Algorithm          | Primary Mechanism   | Time Complexity      | Best Suited For     |+--------------------+---------------------+----------------------+---------------------+| Kruskal's MST      | Edge sort + DSU     | O(E log E)           | Sparse graphs (E ~ V)| Prim's (BinaryHeap)| Vertex relaxation   | O(E log V)           | Standard general    || Prim's (FibHeap)   | Decrease-key        | O(E + V log V)       | Dense graphs (E ~ V2)|+--------------------+---------------------+----------------------+---------------------+

05Production Architecture & Engineering Trade-Offs

Tree-based data structures provide the foundational indexing mechanism for database storage engines and file systems. However, maintaining balanced tree topology under continuous insertion and deletion workloads is non-trivial. While perfectly balanced trees guarantee O(log n) worst-case search latencies, the rotational overhead required to enforce strict balance factors can degrade write performance.

In production database engines such as PostgreSQL or MySQL InnoDB, B+ Trees are favored over binary search trees because their high branching factor minimizes disk I/O and aligns node sizes with operating system virtual memory page boundaries. When operating entirely in memory, Red-Black trees offer an optimal compromise by bounding rebalancing rotations to a small constant number.

LET IT CLICK

The ideas worth keeping.

DSU with path compression and union-by-rank operates in near-constant O(alpha(n)) time.
Kruskal's algorithm greedily unites lowest-weight edges using DSU to prevent cycles.
A minimum spanning tree on V vertices always consists of exactly V - 1 edges.

TURN UNDERSTANDING INTO SOMETHING YOU CAN DO

Make it yours.

Type and test your code right here in the interactive workspace. Run your solution, check the output, and compare with the worked guide when ready.

Exercise 1: How does Path Compression modify the parent p

How does Path Compression modify the parent pointers during a find(x) call?

your_turn_1.java☕Java

Ctrl + ↵

Output

Click Run or press Ctrl+Enter

Output will appear here after you run the code.

Explore a worked solution

one_possible_solution.javaJava

// During find(x), as the recursion traverses up to the root, every visited node// has its parent pointer reassigned directly to the root: parent[x] = find(parent[x]).// This flattens the tree so subsequent calls to any node on that path reach the root in O(1).

All visited nodes on the path are repointed directly to the root.

Exercise 2: Explain how DSU detects a cycle when adding a

Explain how DSU detects a cycle when adding an undirected edge (u, v) to a graph.

your_turn_2.java☕Java

Ctrl + ↵

Output

Click Run or press Ctrl+Enter

Output will appear here after you run the code.

Explore a worked solution

one_possible_solution.javaJava

// Before adding edge (u, v), call find(u) and find(v).// If find(u) == find(v), vertices u and v are already connected through existing edges.// Adding (u, v) would introduce a second path between them, forming a cycle.// If find(u) != find(v), the edge connects two previously disjoint components.

What does it mean if find(u) == find(v) before adding the edge?

Keep exploring.

The official references behind this lesson, when you want a second angle or the full details.

One lesson closer.

Reading is a start. Trying it yourself makes the connection.

Solve the hands-on coding challenge in the knowledge section to verify your code and unlock lesson completion.

By the end, you’ll be able to…

01The Disjoint Set Union (DSU) Abstraction

02The Near-Constant Magic of the Inverse Ackermann Function

03Kruskal's Algorithm for Minimum Spanning Trees (MST)

04Kruskal vs Prim MST Comparison

05Production Architecture & Engineering Trade-Offs

The ideas worth keeping.

Make it yours.

Exercise 1: How does Path Compression modify the parent p

Exercise 2: Explain how DSU detects a cycle when adding a

What stayed with you?

Exercise 1: How does Path Compression modify the parent p

Keep exploring.

One lesson closer.