Number of Connected Components in an Undirected Graph
On this page
Problem statement
You get
nnodes labeled0ton − 1and a list of undirected edges. Return the number of connected components: groups of nodes where every node can reach every other node in the group through edges. A node with no edges is a component by itself.
This is the cleanest union-find question there is, and a common warm-up before harder grouping problems. It can also be solved with BFS or DFS, and interviewers like to hear you compare the two. Original problem: LeetCode 323 (premium).
Example

Input: n = 5, edges = [[0, 1], [1, 2], [3, 4]]
Output: 2
Input: n = 5, edges = [[0, 1], [1, 2], [2, 3], [3, 4]]
Output: 1
Input: n = 4, edges = []
Output: 4 # every node is its own component
Constraints (assumed)
- 1 ≤ n ≤ 2,000.
- 0 ≤ number of edges ≤ 5,000; no duplicate edges; no self-loops.
What this question tests
- Recognizing connected components and choosing between union-find and graph traversal.
- Implementing union-find correctly:
findwith path compression, and a union that only counts real merges. - Handling isolated nodes and cycles.
Questions to ask first
- Are edges undirected? (Yes. For directed graphs, "connected" needs a different definition.)
- Can there be duplicate edges or self-loops? Union-find handles both safely; a counting shortcut does not.
- Do all
nnodes count, even ones that never appear in an edge? (Yes.) - Will edges arrive over time? If so, union-find is the natural fit because it updates incrementally.
Try it yourself first
You have the full problem. Sketch your answer, then sign up free to read the complete walkthrough.
- The complete design, flow by flow, with pictures
- Deep dives into the hard parts
- What mid, senior and staff candidates are expected to say
- Full company question lists
Free forever. No card needed.