28 · Union-Find & Minimum Spanning Trees
#323 Number of Connected Components in an Undirected Graph
the problem
In plain words
A graph has n nodes, numbered 0 to n − 1, and a list of undirected edges edges[i] = [a, b]. Two nodes belong to the same component if you can walk from one to the other along edges. Return how many components the graph has. (A node with no edges is a component on its own.)
in n = 5, edges = [[0,1],[1,2],[3,4]]
out 2
{0, 1, 2} and {3, 4}.
in n = 5, edges = [[0,1],[1,2],[2,3],[3,4]]
out 1
One chain through all five nodes.
- 1 ≤ n ≤ 2000
- 1 ≤ edges.length ≤ 5000
- edges[i] = [a, b] with 0 ≤ a, b < n and a ≠ b
- No repeated edges
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code right here. Stuck for 20 minutes? Open one hint at a time.
This one is LeetCode Premium. You don't need a subscription: solve it right here. The free alternative linked above is the closest free practice; its label says how close it is.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternUnion-Find (DSU)Graph DFS / BFS traversal
Start with n separate nodes = n components. Every edge that joins two different components merges them, so the count drops by exactly one. Edges inside one component change nothing.
solutions
From brute force to optimal
Give every node its own label; keep copying the smaller label across every edge until a full pass changes nothing. Count the labels that survived.
- label[i] = i.
- Repeat: for each edge, set both ends to the smaller of their two labels; note if anything changed.
- Stop after a pass with no change; count nodes with label[i] == i.
A label can move only one edge further per pass in the worst order, so a long path needs up to V passes of E edges each.
One label per node; no adjacency list.
class Solution { /** Everyone starts with their own label; keep copying the smaller label across every edge until nothing changes. */ public int countComponents(int n, int[][] edges) { int[] label = new int[n]; for (int i = 0; i < n; i++) label[i] = i; boolean changed = true; while (changed) { // up to n passes on a long path changed = false; for (int[] e : edges) { int low = Math.min(label[e[0]], label[e[1]]); if (label[e[0]] != low || label[e[1]] != low) { label[e[0]] = low; label[e[1]] = low; changed = true; } } } int count = 0; for (int i = 0; i < n; i++) if (label[i] == i) count++; // one survivor label per component return count; }}Build adjacency lists; each DFS started from an unseen node marks one whole component.
- Build
List<List<Integer>>with both directions of every edge. - For each node not yet seen: count++, DFS to mark its component.
- Return count.
Every node is visited once and every adjacency entry is read once.
Adjacency lists, seen, and recursion up to V deep (a long path).
class Solution { public int countComponents(int n, int[][] edges) { List<List<Integer>> adj = new ArrayList<>(); for (int i = 0; i < n; i++) adj.add(new ArrayList<>()); for (int[] e : edges) { adj.get(e[0]).add(e[1]); adj.get(e[1]).add(e[0]); } boolean[] seen = new boolean[n]; int count = 0; for (int s = 0; s < n; s++) { if (seen[s]) continue; count++; // s was not reached before → a new component dfs(adj, s, seen); } return count; } private void dfs(List<List<Integer>> adj, int u, boolean[] seen) { seen[u] = true; for (int v : adj.get(u)) if (!seen[v]) dfs(adj, v, seen); }}count = n; union the ends of every edge; each union that joins two different roots does count--.
- parent[i] = i, size[i] = 1, count = n.
- For each edge: ra = find(a), rb = find(b).
- ra != rb → hang the smaller tree under the bigger, count--.
O(V) to initialise, then near-constant amortized work per edge.
Only parent and size — no adjacency lists at all.
class Solution { private int[] parent, size; private int find(int x) { if (parent[x] != x) parent[x] = find(parent[x]); return parent[x]; } public int countComponents(int n, int[][] edges) { parent = new int[n]; size = new int[n]; for (int i = 0; i < n; i++) { parent[i] = i; size[i] = 1; } int count = n; // n singletons for (int[] e : edges) { int ra = find(e[0]), rb = find(e[1]); if (ra == rb) continue; // already together: no change if (size[ra] < size[rb]) { int t = ra; ra = rb; rb = t; } parent[rb] = ra; size[ra] += size[rb]; count--; // two components became one } return count; }}in the room
How to say it in the interview
talk track
- Say: "Components start at n; each edge between different components merges two of them."
- Offer DFS (build adjacency lists) and DSU (works straight on the edge list). Pick DSU if edges could arrive over time.
- Mention isolated nodes count — that's why the answer starts from n, not from the number of edges.
traps
- Counting edges instead of merges — an edge inside a component (a cycle) must not change the count.
- Forgetting isolated nodes: they never appear in
edgesbut each one is a component. - Adding only one direction to the adjacency list in the DFS version.
what they ask next
Follow-ups
Edges arrive one at a time and you must report the count after each?
DSU answers every step in near-constant time; a DFS version would recount from scratch, O(V + E) per step.
The same question as a matrix (LC 547)?
Number of Provinces — scan the upper triangle of the matrix and union each 1.
before you submit
Edge cases to test
- Nodes that appear in no edge are components of their own.
- A cycle (triangle) still counts as one component — its third edge must not decrement the count.
- Edges listed backwards along a long path: a recursive DFS goes deep (up to n = 2000 calls) — fine here, but mention the iterative option.
practise next
Similar problems
- #547Number of ProvincesMediumin Union-Find & MST
- #200Number of IslandsMediumin Graphs
- #1319Number of Operations to Make Network ConnectedMediumin Union-Find & MST