Union Find (DSU)

Union Find Basics

Each node starts as its own parent. find(x) follows parent pointers to the root. union(x,y) makes one root point to the other. Path compression: during find(), make every node on the path point directly to the root.

O(α(n)) per op

O(n)

How It Works

Union-find (disjoint set union) maintains a partition of elements into groups under two operations: find(x) returns the representative (root) of x's group, and union(x, y) merges two groups. Each element stores a parent pointer; roots point to themselves. find follows parents to the root, and union simply makes one root the parent of the other. Path compression turbocharges find: on the way back from the root, every visited node is re-pointed directly at the root, flattening the tree for all future queries.

With path compression (and union by rank) the amortized cost per operation is O(alpha(n)) — the inverse Ackermann function, below 5 for any realistic input, effectively constant. This is why union-find beats re-running DFS after every edge insertion: it answers dynamic connectivity queries incrementally in near-constant time.

Step-by-Step Visualization

Each node is its own parent initially

parent[0,1,2,3,4]

1/4

Code

Java

class UnionFind {
  int[] parent, rank;

  UnionFind(int n) {
    parent = new int[n];
    rank = new int[n];
    for (int i = 0; i < n; i++) parent[i] = i;
  }

  int find(int x) {
    if (parent[x] != x)
      parent[x] = find(parent[x]); // Path compression
    return parent[x];
  }

  boolean union(int x, int y) {
    int px = find(x), py = find(y);
    if (px == py) return false;
    if (rank[px] < rank[py]) parent[px] = py;
    else if (rank[px] > rank[py]) parent[py] = px;
    else { parent[py] = px; rank[px]++; }
    return true;
  }
}

Tips & Gotchas

1find(x) follows parent pointers to root — use path compression

2union(x, y) merges the sets containing x and y

3With path compression and union by rank, nearly O(1) per operation

Practice Problems

1Number of Provinces
2Redundant Connection
3Accounts Merge
4Graph Valid Tree
5Smallest String With Swaps

About the Union Find (DSU) Pattern

Track which nodes are in the same connected component. Supports two operations: find(x) returns x's group leader, union(x,y) merges two groups. With path compression and union by rank, both operations are nearly O(1).

Key insight

Start with: is it directed or undirected? Weighted or unweighted? Then pick the right tool: BFS for shortest unweighted path, Dijkstra for weighted, topological sort for DAG ordering, union-find for components.

Common Graphs Interview Problems

Number of Islands
Clone Graph
Course Schedule
Pacific Atlantic Water Flow
Network Delay Time
Minimum Spanning Tree
Word Ladder

Frequently Asked Questions

When should I reach for union-find instead of DFS or BFS?

Use union-find when edges arrive incrementally or you must answer connectivity queries interleaved with merges — DFS would need to re-traverse after every change. If the graph is fully given and you only need components once, a single DFS/BFS pass is equally good and needs no extra data structure.

Is path compression alone enough, without union by rank?

In practice yes for most interview inputs — path compression alone gives O(log n) amortized, which is plenty. Adding union by rank or size tightens the bound to inverse Ackermann and costs only one extra array, so it is worth mentioning even if you skip it under time pressure.

Can union-find handle edge deletions?

Not directly — the structure only merges, never splits, because compression destroys the original tree shape. Deletion problems are usually solved offline by reversing time: process operations backward so deletions become insertions.