LeetCode 323 · Medium · Graphs

Number of Connected Components in an Undirected Graph

Given n nodes labelled 0 to n − 1 and a list of undirected edges, return how many connected pieces the graph falls into.

O(V + E·α(V))time
O(V)space
union-findeach join removes one piece

n 1–10 · up to 12 distinct pairs [u, v], nodes 0 to n − 1, no self-loops

par par[i] = parent of i · a root points to itself (green)

rank size of the tree under each root

private int[] par;private int[] rank;public int countComponents(int n, int[][] edges) { par = new int[n]; rank = new int[n]; for (int i = 0; i < n; i++) { par[i] = i; rank[i] = 1; } int res = n; for (int[] e : edges) { res -= union(e[0], e[1]); } return res;}private int find(int n1) { int res = n1; while (res != par[res]) { par[res] = par[par[res]]; // path halving res = par[res]; } return res;}private int union(int n1, int n2) { int p1 = find(n1); int p2 = find(n2); if (p1 == p2) { return 0; } if (rank[p2] > rank[p1]) { par[p1] = p2; rank[p2] += rank[p1]; } else { par[p2] = p1; rank[p1] += rank[p2]; } return 1;}
res
—
[n1, n2]
—
p1
—
p2
—
rank[p1], rank[p2]
—

Why it works

  1. Brute force is already decent: build an adjacency list and start a DFS from every unvisited node, counting the starts, in O(V + E). Union-find gets the same count without an adjacency list, one edge at a time.
  2. Invariant: res equals the number of distinct roots. It starts at n (every node alone), and an edge between two different roots merges two pieces into one: res -= 1. An edge whose ends share a root changes nothing.
  3. O(V + E·α(V)): union by rank keeps trees shallow and path halving flattens them as find walks, so each find is nearly O(1).
  4. Pitfall: compare roots, not direct parents. In the "pairs of pairs" preset, after edge [1, 3] node 1 hangs under 0 and node 3 under 2, yet both have root 0. Only find can tell.
  5. Related: Graph Valid Tree (261) is "one piece and exactly n − 1 edges"; Redundant Connection (684) returns the first edge whose ends already share a root.