Number of connected components in an undirected graph

Given n vertices and a list of undirected edges, return the number of connected components.

Before you code

Each search from an unvisited vertex marks one whole component, so the number of searches you start is the answer. Isolated vertices count as components too.

Hints

1. Build adjacency lists.
2. Loop over all vertices; for each unvisited one, add 1 and run BFS or DFS.
3. Union-find solves it without adjacency lists: start with n components and subtract 1 for every edge that joins two different sets.

Production & complexity notes

When solving Number of connected components in an undirected graph on LeetCode (medium), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Cycles and connected components to reinforce the underlying pattern.

What it practices

Counting components, from Cycles and connected components.