‹ DS&A interview · Socratic
DSA · Graph · #130

Number of Connected Components in an Undirected Graph

Module 43 · difficulty 3/5·⏱ 30:00starts on first keystroke

You are given an integer `n`, the number of nodes in an undirected graph labeled `0` to `n - 1`, and a list `edges` where `edges[i] = [a, b]` indicates an undirected edge between nodes `a` and `b`. Implement `countComponents(n, edges)` that returns the number of connected components in the graph.

Examples
  • n = 5, edges = [[0,1],[1,2],[3,4]] → 2 — {0,1,2} form one component and {3,4} form another.
  • n = 5, edges = [[0,1],[1,2],[2,3],[3,4]] → 1 — All nodes are chained together into a single component.
  • n = 4, edges = [] → 4 — With no edges, every node is its own component.
Constraints
  • · 1 <= n <= 2000
  • · 0 <= edges.length <= 5000
  • · edges[i].length == 2
  • · 0 <= a, b < n
  • · a != b
  • · There are no repeated edges.
Session phases
A · Clarify
B · Approach
C · Complexity
D · Edges
E · Code
F · Tradeoff
G · Score
Phase A — Clarify
Ask questions about input bounds, types, and edge constraints.
Ask the coach clarifying questions about the problem.
When you've covered this phase, advance to the next.