Number of Connected Components in an Undirected Graph
FreeGraphsMedium47 of 75
The problem
Count connected components among n vertices labeled 0 through n−1, including isolated vertices, given a list of undirected edges.
Example
n = 5, edges = [[0, 1], [1, 2], [3, 4]] → 2
Need a hint?
A traversal from an unseen vertex visits exactly one component.
Write pseudocode, trace the example, or note an edge case. This scratchpad does not run code.
Notes stay in this browser when storage is available.
Read the solution approach
Build adjacency lists. Iterate through all n vertices; each unvisited vertex starts a traversal and increases the component count. Mark vertices as they enter the stack or queue. An isolated vertex is a component of size one.
Complexity
O(n + E) time and space.
Before moving on, explain why the algorithm is correct and trace a boundary case without looking at the approach.