Example 1
ready- Input
n = 5 edges = [ [ 0, 1 ], [ 1, 2 ], [ 3, 4 ] ]- Expected
2- Why
- 0-1-2 form one group; 3-4 form the other
Connected Components
35 min · countComponents()mediumOpen in LeetCode #323 ↗
Imagine a company chat where some coworkers can reach each other through chains of introductions, while other groups remain completely separate. How many groups are there?
You're given n nodes labeled from 0 through n - 1. Each pair [a, b] is an
undirected edge, so the connection works in both directions. Return the number of
connected components — separate groups where every node can reach every other node,
and no edge reaches a node outside the group.
A node with no edges forms a component by itself. Loops don't create extra components; they only add more routes inside an existing one.
Constraints
1 <= n <= 2_0000 <= edges.length <= 5_000- Every edge contains two node labels in the range
0..n - 1. - There are no self-loops and no duplicate undirected edges.
Hints
One search, one group
Start from an unseen node and visit everything reachable from it. That entire walk discovers exactly one connected component.
Don't lose the loners
Iterate over all n node labels, not just labels that appear in edges. An isolated
node still increases the answer.
Count successful merges
Union-find starts with n separate groups. Reduce the count only when an edge joins
two roots that were previously different.
Follow-up
If new edges keep arriving, can you report the component count after each one without traversing the whole graph again?
Visible cases
Examples
Example 2
ready- Input
n = 5 edges = [ [ 0, 1 ], [ 1, 2 ], [ 2, 3 ], [ 3, 4 ] ]- Expected
1- Why
- the chain reaches all five nodes
Example 3
ready- Input
n = 4 edges = []- Expected
4- Why
- without edges, every node stands alone
Interview signal
Asked at
AmazonGoogle
Graph traversal — launch one search per component
Build an adjacency list, a list of every node's neighbors, and keep one seen array.
Whenever the outer loop reaches an unseen node, you've found a new connected component.
Count it, then breadth-first search from that node and mark the whole group.
from collections import deque
def count_components(n: int, edges: list[list[int]]) -> int:
graph = [[] for _ in range(n)]
for a, b in edges:
graph[a].append(b)
graph[b].append(a)
seen = [False] * n
components = 0
for start in range(n):
if seen[start]:
continue
components += 1
seen[start] = True
queue = deque([start])
while queue:
node = queue.popleft()
for neighbor in graph[node]:
if not seen[neighbor]:
seen[neighbor] = True
queue.append(neighbor)
return componentsTime O(V + E), space O(V + E) — every node enters the queue once, every edge is read twice, and the adjacency list stores both directions.
Union-find — begin apart, merge on demand
Union-find, also called disjoint-set union, represents every connected group by one
root. Begin with n roots and a component count of n. For each edge, merge its roots
only if they're different; every successful merge reduces the count by one.
def count_components(n: int, edges: list[list[int]]) -> int:
parent = list(range(n))
size = [1] * n
components = n
def find(node: int) -> int:
while node != parent[node]:
parent[node] = parent[parent[node]]
node = parent[node]
return node
for a, b in edges:
root_a = find(a)
root_b = find(b)
if root_a == root_b:
continue
if size[root_a] < size[root_b]:
root_a, root_b = root_b, root_a
parent[root_b] = root_a
size[root_a] += size[root_b]
components -= 1
return componentsPath compression and union by size make each root lookup effectively constant. More
precisely, the edge work costs α(V) amortized, where α is the inverse Ackermann
function.
Time O(V + E·α(V)), space O(V) for the parent and size arrays.
Traversal asks, “what belongs to this group?” Union-find asks, “do these two nodes already belong together?” Choose based on whether your graph is static or keeps gaining edges.
Loading editor
Console
ready to runReady to run.
3 cases are queued.
Visible testcase
Case 1
Expected
2
Run: visible + custom · Submit: full suite