Compile Ready
Module 2 · Connected Components

Number of Connected Components in an Undirected Graph

MediumProblem 6 of 25 8 min read ~20 min to solve LeetCode
GraphUnion FindDFSBFS
Asked atAmazonMicrosoftGoogleMetaBloomberg

Problem Statement

You are given n nodes labelled 0..n-1 and an undirected edge list edges, where edges[i] = [a, b] means there is a bidirectional connection between a and b.

Return the number of connected components in the graph. A connected component is a maximal group of nodes where every node can reach every other node in that group through some path.

Input

An integer n and a 2D integer array edges representing an undirected graph over nodes 0..n-1.

Output

An integer: the number of connected components.

Constraints

  • •1 <= n <= 2000
  • •0 <= edges.length <= 5000
  • •edges[i].length == 2
  • •0 <= ai, bi < n
  • •ai != bi
  • •There are no repeated edges.

Examples

Example 1

Input: 
n = 5, edges = [[0,1],[1,2],[3,4]]
Output: 2
Explanation: Nodes {0,1,2} form one component, and nodes {3,4} form another.

Example 2

Input: 
n = 5, edges = [[0,1],[1,2],[2,3],[3,4]]
Output: 1
Explanation: Every node is connected through the chain 0-1-2-3-4, so the whole graph is one component.

Learning Objectives

  • Recognise connected-components counting as repeated reachability over an undirected graph.
  • Use Union-Find to maintain components by merging sets and decrementing the component count only on successful merges.
  • Build an adjacency list and count how many BFS or DFS traversals are needed to cover all vertices.
  • Choose between Union-Find and traversal based on whether edges are streaming or the graph is already materialised.

Intuition

A connected component is a group identity: all nodes inside it are mutually reachable, and no edge connects it to another group. Initially, with no edges processed, every node is its own group, so the answer starts at n. Each edge can do only one meaningful thing: if its endpoints are in different groups, it merges those groups and the component count drops by one; if they are already in the same group, it adds a cycle and the count does not change.

That observation is exactly what Union-Find models. It lets you process edges one by one without building the whole graph, which is why it is excellent for streaming or incremental connectivity questions.

The traversal view is equally important: build the adjacency list, then every time the outer loop finds an unvisited node, that node is the seed of a new component. One BFS or DFS from that seed marks the entire component, so the number of seeds you needed is the number of components.

Recognise the pattern: if a problem asks how many separate groups exist in an undirected edge list, either union endpoints and count merges, or traverse from each unvisited seed.

Common mistakes

  • ×Decrementing the component count for every edge instead of only for edges whose endpoints were in different components.
  • ×Building an adjacency list in only one direction even though the graph is undirected.
  • ×Assuming components equal n - edges.length; cycles make that formula wrong.
  • ×Forgetting isolated nodes: a node with no incident edges is still a component.
  • ×Using recursive DFS without discussing stack depth when n can be large; iterative BFS or Union-Find is safer.

Algorithm Explanation

Union-Find: start with components = n. Each node is its own parent. For every edge [u, v], find the roots of u and v. If the roots differ, union the smaller-rank tree under the larger-rank tree and decrement components. At the end, components is the answer.

Traversal: build an adjacency list with both directions for every edge. Keep a visited array. Scan nodes 0..n-1; when a node is unvisited, increment components and BFS or DFS from it to mark every reachable node. The number of traversals started is the answer.

Solutions

Solution 1: Union-Find with rank and path compression

When to prefer this:

Ideal when edges arrive incrementally, when you may need to answer many connectivity questions, or when you want to count components without storing adjacency lists.

Represent each component by a root. Path compression makes future root lookups fast, and union by rank keeps trees shallow. The key invariant is that components decreases exactly once per successful merge.

Step-by-step

  1. Initialise parent[i] = i and rank[i] = 0 for every node.
  2. Set components = n.
  3. For each edge, find both roots. If they match, the edge stays inside one component, so do nothing.
  4. If roots differ, attach the lower-rank root under the higher-rank root, increasing rank on ties, and decrement components.
  5. Return components after all edges are processed.
Time

O(n + E · α(n))

Space

O(n)

α is the inverse-Ackermann function, effectively constant for interview-sized inputs.

Java implementation

Loading…

Solution 2: BFS over an adjacency list

When to prefer this:

Simplest when the graph is already built or when follow-ups may ask for actual members of each component. It is also easy to adapt to return the component lists.

Build neighbours for every node, then run an iterative BFS from each unvisited seed. Each BFS consumes exactly one component, so the number of BFS launches is the answer.

Step-by-step

  1. Create an empty list of neighbours for each node.
  2. Add each undirected edge in both directions.
  3. Scan every node. If it is already visited, it belongs to a component discovered earlier.
  4. If it is unvisited, increment the component count and BFS from it, marking neighbours at enqueue time.
  5. Return the total number of BFS launches.
Time

O(n + E)

Space

O(n + E)

The adjacency list stores each undirected edge twice; visited and queue are O(n).

Java implementation

Loading…

Dry Run

Sample input

n = 5, edges = [[0,1],[1,2],[3,4]]. Union-Find starts with five singleton components: {0}, {1}, {2}, {3}, {4}.

EdgeOperationComponentsReason
startnone5Every node is isolated.
[0,1]union 0 and 14Two singleton components merge.
[1,2]union root(1) with 23Node 2 joins {0,1}.
[3,4]union 3 and 42A second component forms.
donereturn2Components are {0,1,2} and {3,4}.

Each successful union reduces the count by one. No edge connects the two groups, so the final answer is 2.

Interview Tips

Lead with the invariant: each successful merge reduces the number of components by one. That single sentence explains why Union-Find is correct. Then mention the traversal alternative, because some interviewers prefer the adjacency-list view and may ask for the actual groups. For Senior/Staff interviews, explicitly contrast the two: Union-Find is operationally better for streaming edges and many queries; BFS or DFS is better when you already have the graph and need to enumerate component members.

Likely follow-ups

  • Return the list of nodes in each connected component, not just the count.
  • Edges arrive online and after each insertion you must report the current component count.
  • Support deletion of edges; why is plain Union-Find no longer enough?
  • Determine whether the graph is a valid tree by combining component count with the edge-count condition.

Similar Problems

Number of Provinces
MediumSame component counting, but the graph is given as an adjacency matrix.
Find if Path Exists in Graph
EasySingle-pair connectivity instead of counting all components.
Graph Valid Tree
MediumA tree must be connected and have exactly n - 1 edges.
Redundant Connection
MediumUnion-Find detects the edge that tries to merge nodes already connected.

Key Takeaways

  • Connected components are maximal reachability groups.
  • Union-Find count starts at n and decreases only on successful unions.
  • Traversal count increments once per unvisited seed, then marks the whole component.
  • Cycles do not change the number of components.
Reusable template: Connected-components count: union every undirected edge and count successful merges, or run one BFS or DFS from each unvisited seed.