Number of Connected Components in an Undirected Graph
Number of Connected Components in an Undirected Graph: given n nodes and a list of undirected edges, count how many connected components the graph has.
- 1 <= n <= 2000
- 1 <= edges.length <= 5000
- edges[i].length == 2
- There are no repeated edges and no self-loops.
Intuition
Number of connected components in an undirected graph counts the separate groups of nodes in a graph given as an edge list. Two nodes belong to the same component when a path connects them.
Two approaches solve it, and they think about the problem differently.
The traversal approach starts a DFS or BFS from every unvisited node. Each launch reaches exactly one full component and marks it, so:
- The number of times a fresh traversal has to be started is precisely the number of components.
That requires building an adjacency list first, with both directions per edge — omitting the reverse entry splits components that are genuinely connected.
The Union-Find approach never builds a graph. Start with n components, one per node, and union the endpoints of each edge. A union that actually merges two distinct sets decrements the count; a union of nodes already together changes nothing.
That conditional decrement is where implementations go wrong. Decrementing on every edge ignores redundant edges within a component and undercounts badly on dense graphs.
Isolated nodes with no edges are handled correctly by both — the traversal finds them as single-node components, and Union-Find counts them from the initial n.
The traversal is O(V + E) with O(V + E) space for the adjacency list; Union-Find is near-linear at O(E · α(V)) with only O(V) space, and needs no adjacency structure at all.
Union-Find suits this particular problem well, since the input is already an edge list and only a count is required — not the components themselves.
Counting connected components is the archetypal 'traverse from every unvisited node' problem, and the same outer-loop-plus-flood-fill shape solves Number of Islands, Number of Provinces, and Max Area of Island. The tell is a question about groups rather than paths.
Approach
Before reading on: if you begin a traversal at an unvisited node, what exactly have you discovered by the time it finishes? How does that let you count components without any extra bookkeeping? Aim for O(n + e).
Count traversal launches
Start a DFS or BFS from each unvisited node. Each launch covers exactly one component, so the number of launches is the answer.
Build both edge directions
For the traversal approach, add each edge to both adjacency lists. Omitting the reverse entry splits components that are genuinely connected.
Or start Union-Find at n
Begin with n components, one per node. Each node is initially its own set, which correctly counts isolated nodes with no edges.
Decrement only on a real merge
Reduce the count only when a union joins two distinct sets. Decrementing on every edge undercounts badly, since redundant edges within a component merge nothing.
Skip the adjacency list entirely
Union-Find works straight from the edge list, needing no graph structure — a real advantage when only the count is required.
Cost of each approach
Traversal is O(V + E) time with O(V + E) space. Union-Find is O(E · α(V)) — effectively linear — with only O(V) space.
Solution & live demo
Common pitfalls
Adding edges in only one direction
adjacency[a].append(b)
adjacency[a].append(b) adjacency[b].append(a)
The graph is undirected, so both endpoints must know about the edge. With one direction the traversal cannot walk backwards and one component gets counted as several.
Counting nodes instead of traversal starts
components = len(visited)
components += 1 # once per fresh start
The number of visited nodes is n once everything is explored. It is the number of times a traversal had to be started that equals the component count.
Only traversing from node 0
dfs(0) return 1
for start in range(n):
if not visited[start]: ...A single traversal reaches only the component containing node 0. Every node must be tried as a potential start, or disconnected components are never discovered.
Edge cases
Every node is isolated, so the answer is n.
One traversal covers everything and the answer is 1.
The outer loop reaches it, starts a traversal that visits only it, and counts it as its own component.
The visited check makes a repeated edge a no-op.
The node is already visited when the loop is followed, so nothing changes.