Problem Statement
Number of Connected Components
You have a graph with n nodes, numbered 0 to n-1. You are given that number n and a list called edges. Each entry edges[i] = [ai, bi] is a wire that connects node ai to node bi. Your job is to count the connected components. A connected component is a group of nodes where you can travel from any node to any other node in that group by following wires. Nodes with no wire between them, directly or through other nodes, belong to different groups. The tool that fits this perfectly is Union-Find, also called Disjoint Set Union. Think of it like groups of friends. Each person starts alone. When you learn that two people are friends, you merge their two friend circles into one. Union-Find lets you quickly ask "which circle is this person in?" and "merge these two circles." That is exactly what counting connected components needs.
Signals to notice
Brute force first
For each unvisited node, DFS/BFS to find its component. This IS the standard approach; Union-Find offers a different angle. That direct path helps you understand the question, but it tends to treat every possibility as brand new instead of learning from earlier steps.
The key insight
Union-Find: initially each node is its own component. For each edge, union the two nodes. Count the number of distinct roots at the end. The goal is not to be clever for its own sake, but to remember the one relationship that keeps the solution grounded as you move forward.
Trace it on n=5, edges=[[0,1],[1,2],[3,4]]
init: parent=[0,1,2,3,4], rank=[0,0,0,0,0], components=5
union(0,1): roots 0!=1, equal rank -> parent[1]=0, rank[0]=1, components=4
union(1,2): find(1)=0, find(2)=2; 0!=2, rank[0]>rank[2] -> parent[2]=0, components=3
union(3,4): roots 3!=4, equal rank -> parent[4]=3, rank[3]=1, components=2
edges done; distinct roots: {0} for nodes 0,1,2 and {3} for nodes 3,4
return components = 2What must stay true
Two nodes in the same component share the same root in the Union-Find structure. The number of distinct roots = number of connected components. As long as that statement keeps holding, you can trust the steps built on top of it.
Shape of the loop
parent = [0..n-1]; rank = [0]*n; components = n
find(x): follow parent to root, compress path
union(x,y): rx,ry = find(x),find(y); if rx==ry return
attach lower-rank root under higher (bump rank on tie); components -= 1
for (a,b) in edges: union(a,b)
return componentsPseudocode only — the full worked solution lives in the Solution tab.
Easy way to go wrong
Forgetting path compression and union by rank — without them, Union-Find degrades to per operation. With both optimizations, it's nearly amortized. Most mistakes here are not about syntax; they come from losing track of what your state, pointer, or structure is supposed to mean.