Number of Connected Components

Given an undirected graph with V vertices (0 .. V-1) and an edge list edges, return the number of connected components — maximal groups of vertices that are all reachable from one another. Isolated vertices count as their own component.

Hints

· Stuck? Reveal one nudge at a time.

A component is everything reachable from one vertex — flood it.

Each unvisited vertex you start from is exactly one new component.

Union-Find alternative: start count at V and subtract one for every edge that merges two different sets.

Common doubts

When edges arrive one at a time (a stream) — it maintains the running component count in near-O(1) amortized per edge, without rebuilding a traversal.

An edge within an existing component doesn't change connectivity; only edges that join two distinct sets reduce the count.

Path compression alone already gives near-constant amortized finds here; union by rank/size makes it provably near-linear.

Interview follow-ups

· What an interviewer asks next.

Track a size array in union-find, or count nodes during each flood.

A grid is a graph whose edges connect adjacent land cells; islands are its connected components.

Fun facts

Union-Find with path compression + union by rank has near-constant amortized cost — the inverse-Ackermann function α grows slower than any practical log.
Counting components is the 'hello world' of both DFS and DSU.

Asked at

AmazonMicrosoftGoogle

Frequently Sometimes Occasionally

Example 1

Input: V = 5, edges = [[0,1],[1,2],[3,4]]
Output: 2
{0,1,2} and {3,4} are the two components.

Example 2

Input: V = 3, edges = []
Output: 3
Three isolated vertices are three components.

Constraints

- 1 <= V <= 10^5 - 0 <= edges.length <= 10^5 - 0 <= u, v < V - u != v

A connected component is a maximal reachable group. Two standard ways to count them:

Flood each component (DFS/BFS). Walk from every unvisited vertex, marking everything reachable; each fresh start is one new component. O(V + E).

Union-Find (DSU). Start with V singletons and a counter at V. For each edge, union its endpoints; every union that actually merges two different sets decrements the counter. What remains is the component count. With path compression it's near-O(V + E·α), and it shines when edges arrive incrementally (you get the running count for free).

Prerequisites

Before you start

· Concepts used directly in the solution.

Flood fill. visit all vertices reachable from a start.

Union-Find. find (with path compression) + union; a merge shrinks the component count.

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

Setup

“Do isolated vertices count?”

Yes — each is its own component.

“Undirected?”

Yes; add each edge both ways in the adjacency list.

The ideal opening — say it like this

I flood each unvisited vertex — each new flood is one component — or use union-find and count how many merges happen.

Both are near-linear; union-find is nicer when edges stream in.

Understand the problem

Worked example — V = 5, edges [[0,1],[1,2],[3,4]]

flood 0 -> {0,1,2}   (component 1)
flood 3 -> {3,4}     (component 2)
answer = 2

Key observations

1Aha

Each new flood = one component

Restarting on an unvisited vertex discovers exactly one component.

2Aha

A real union shrinks the count

Start at V; each merge of two different sets subtracts one.

3Aha

Both are near-linear

O(V+E) flooding; O(V + E·α) with union-find.

Brute force vs optimal

	Flood fill (DFS)	Union-Find
Idea	Traverse each unvisited vertex	Merge edge endpoints, count merges
Time	O(V+E)	~O(V + E·α)
Best when	graph given up front	edges arrive incrementally

Both count the same components. Full code is in the Approaches selector below.

Summary

Key takeaway

Count components by flooding each unvisited vertex (one flood = one component), or with union-find starting at V and subtracting one per real merge. Near-linear either way.

flood: for v in V: if unvisited: count++, dfs(v)
dsu:   count = V; for (u,v): if union(u,v) merged: count--