Graphs - Union-Find & MST

important mid - part of Skills & Topics - Senior SWE Roadmap - related: Graphs - BFS and DFS - Graphs - Shortest Path - Greedy Algorithms - Big-O and Complexity Analysis

Why this matters / recognition signals

Union-Find (Disjoint Set Union, DSU) is the right tool when the problem is really about connected components that evolve over time: adding edges, checking whether two nodes are already connected, or merging groups. Minimum spanning tree problems are the most common interview use case: Kruskal’s algorithm sorts edges by weight and uses Union-Find to accept the next light edge that does not create a cycle.

Reach for this when the problem says:

• “are these two nodes in the same group/component?” → connectivity checks
• “merge these sets” / “union these accounts” / “friend circles” → DSU
• “detect whether adding this edge creates a cycle” → DSU
• “minimum spanning tree” / “connect all nodes with minimum cost” → Kruskal + DSU
• “dynamic connectivity” with mostly merge/check operations → DSU

Core idea: represent sets by a parent forest

Each element starts as its own singleton set. A find(x) operation walks parent pointers until it reaches the root representative of x’s set. A union(a, b) operation finds both roots and makes one root point to the other.

Two optimizations make the structure effectively constant time for interview-scale inputs:

• Path compression: after find(x) discovers the root, make every node on the path point directly to that root.
• Union by size/rank: always attach the smaller tree under the larger one, so the forest stays shallow.

flowchart TD
    A1["1 -> 2 -> 3"] -->|find(1) compresses path| A2["1 -> 3
2 -> 3
3 is root"]
    B1["set {4,5}"] -->|union(3,4)| B2["larger root stays shallow"]

The key invariant is simple: each set has exactly one root, and every element points upward toward that root. find() returns the root, so two items are in the same set exactly when their roots match.

Worked example: unioning components

Start with {1},{2},{3},{4},{5}.

Operation	Parent links	Result
union(1, 2)	2 → 1	{1,2}, {3}, {4}, {5}
union(3, 4)	4 → 3	{1,2}, {3,4}, {5}
union(2, 3)	3’s root joins 1’s root	{1,2,3,4}, {5}
find(4)	compress 4 → 1	4 now points directly to the component root

Without path compression, repeated find() calls would keep walking the same chain. With compression, the first expensive lookup pays to flatten the tree, and later lookups become one or two pointer hops.

Kruskal’s algorithm for MST

Kruskal is greedy: sort all edges by weight, then scan them from lightest to heaviest. Accept an edge if and only if its endpoints are currently in different DSU sets; otherwise skip it because that edge would create a cycle.

flowchart LR
    E1["sorted edges by weight"] --> E2["take lightest edge"] --> E3{"same DSU set?"}
    E3 -->|no| E4["accept edge, union sets"]
    E3 -->|yes| E5["skip edge, it would form a cycle"]

Why the greedy choice is safe: if an edge is the cheapest way to connect two currently separate components, any cheaper alternative would already have appeared earlier in the sorted order. Accepting the edge cannot hurt because it increases connectivity while preserving the acyclic structure needed for a tree.

Java implementations

Union-Find

class UnionFind {
    private final int[] parent;
    private final int[] size;
 
    public UnionFind(int n) {
        parent = new int[n];
        size = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }
 
    public int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
 
    public boolean union(int a, int b) {
        int rootA = find(a);
        int rootB = find(b);
        if (rootA == rootB) {
            return false;
        }
 
        if (size[rootA] < size[rootB]) {
            int temp = rootA;
            rootA = rootB;
            rootB = temp;
        }
 
        parent[rootB] = rootA;
        size[rootA] += size[rootB];
        return true;
    }
}

Kruskal MST

import java.util.Arrays;
 
class Solution {
    public int minimumCost(int n, int[][] edges) {
        Arrays.sort(edges, (a, b) -> Integer.compare(a[2], b[2]));
        UnionFind uf = new UnionFind(n);
        int total = 0;
        int used = 0;
 
        for (int[] edge : edges) {
            if (uf.union(edge[0], edge[1])) {
                total += edge[2];
                used++;
                if (used == n - 1) {
                    break;
                }
            }
        }
 
        return used == n - 1 ? total : -1;
    }
}

Python implementations

Union-Find

class UnionFind:
    def __init__(self, n: int) -> None:
        self.parent = list(range(n))
        self.size = [1] * n
 
    def find(self, x: int) -> int:
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
 
    def union(self, a: int, b: int) -> bool:
        root_a = self.find(a)
        root_b = self.find(b)
        if root_a == root_b:
            return False
 
        if self.size[root_a] < self.size[root_b]:
            root_a, root_b = root_b, root_a
 
        self.parent[root_b] = root_a
        self.size[root_a] += self.size[root_b]
        return True

Kruskal MST

def minimum_cost(n: int, edges: list[list[int]]) -> int:
    edges.sort(key=lambda edge: edge[2])
    uf = UnionFind(n)
    total = 0
    used = 0
 
    for u, v, weight in edges:
        if uf.union(u, v):
            total += weight
            used += 1
            if used == n - 1:
                break
 
    return total if used == n - 1 else -1

Common pitfalls

• Forgetting path compression: the algorithm still works, but repeated find() calls stay slow because long chains never flatten.
• Using DSU for directed connectivity: Union-Find models undirected connectivity. If direction matters, you need a different graph algorithm.
• Skipping the cycle check in Kruskal: accepting every edge in sorted order builds a cycle-heavy graph, not a tree.
• Assuming MST is unique: equal-weight edges can produce multiple valid MSTs with the same total cost.

Practice problems

• Number of Connected Components
• Redundant Connection
• Accounts Merge
• Graph Valid Tree
• Min Cost to Connect All Points
• Kruskal-style MST construction problems

Interview angles

• “Why is Union-Find so fast in practice?” - path compression and union by size/rank keep trees extremely shallow, so repeated operations are effectively constant time.
• “Why does Kruskal need DSU?” - to check whether the next light edge connects two different components or would create a cycle.
• “When would you not use DSU?” - when the graph is directed, when you need path details instead of just component membership, or when merges are not the main operation.