Union Find (DSU)

Connected Components

After processing all edges with union(), count the number of distinct roots (nodes where parent[i] == i). Each root represents one connected component. Useful for 'number of islands', friend groups, etc.

O(V * α(V))

O(V)

How It Works

Counting connected components with union-find is a two-phase pattern. Start with n components — every node its own root. Process each edge with union(u, v); whenever the union actually merges two different roots, decrement the component counter. After all edges, the counter holds the number of connected components directly, or you can count nodes whose parent is themselves. This turns a structural question about the graph into simple bookkeeping over merge events.

The total cost is O(E · alpha(n)) after the O(n) initialization, essentially linear in the number of edges. The pattern generalizes far beyond explicit graphs: treat grid cells, email accounts, or array indices as nodes, and union anything the problem declares 'connected'. Dynamic versions, where edges or nodes appear over time and the count is queried after each step, are where union-find decisively beats repeated DFS.

Step-by-Step Visualization

5 nodes, edges: (0,1), (2,3). Count components

Components5 (initial)

1/3

Code

Java

static int countComponents(int n, int[][] edges) {
  UnionFind uf = new UnionFind(n);
  for (int[] e : edges) uf.union(e[0], e[1]);

  Set<Integer> roots = new HashSet<>();
  for (int i = 0; i < n; i++) roots.add(uf.find(i));
  return roots.size();
}

Tips & Gotchas

1Process all edges with union(). Count distinct roots

2Number of components = number of nodes where parent[i] === i

3Useful for counting islands, connected groups

Practice Problems

1Number of Provinces
2Number of Islands II
3Number of Operations to Make Network Connected
4Count Unreachable Pairs of Nodes in an Undirected Graph

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

Should I decrement a counter or count roots at the end?

Both work for a static graph, but the decrement-on-merge approach is essential when the problem asks for the component count after each incremental change, as in Number of Islands II. Counting roots at the end requires a full O(n) scan and be careful to check parent[i] == i on the raw array, or call find(i) to be safe.

How do I map a 2D grid onto union-find?

Flatten each cell (r, c) to the integer r * cols + c and union it with adjacent land cells. Only allocate or activate entries for valid cells, and remember that isolated land with no neighbors still counts as its own component.