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
Start a traversal from every node that has not been seen. Each fresh start discovers one entire component and marks all of it visited, so the number of starts equals the number of components. Isolated nodes are handled for free — they simply form components of size one.
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).
Build an adjacency list first
The edge list is the wrong shape for traversal: finding a node's neighbours would mean scanning every edge. Convert to an adjacency list where entry i holds the nodes adjacent to i. Since the graph is undirected, each edge is added in both directions — omitting one direction turns the graph directed and silently splits components apart. Building the list is O(n + e).
Count the fresh starts
Loop over all nodes from 0 to n-1. If a node is unvisited, increment the component counter and run a DFS or BFS that marks everything reachable from it. Any node reached during that traversal belongs to the same component and will be skipped by the outer loop later. So the counter increments exactly once per component, and the outer loop guarantees no component is missed regardless of how the nodes are numbered.
Union-Find as the alternative
The same count comes from a disjoint-set structure: start with n components, and each edge that joins two different sets reduces the count by one. With path compression and union by rank each operation is effectively constant, giving O(n + e·α(n)). Traversal is simpler to write and equally fast here; Union-Find earns its place when edges arrive incrementally or when you must answer connectivity queries as you go.
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.