Skip to main content

323. Number of Connected Components in an Undirected Graph

medium

Given n nodes and a list of undirected edges, count the connected components. The cleanest introduction to Union-Find — and a useful warm-up before harder DSU problems like Redundant Connection or Accounts Merge.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

You have a graph of n nodes. You are given an integer n and an array edges where edges[i] = [ai, bi] indicates that there is an edge between ai and bi in the graph. Return the number of connected components in the graph.

Constraints

  • 1 <= n <= 2000
  • 1 <= 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

Example 2

Input
n = 5, edges = [[0,1],[1,2],[2,3],[3,4]]
Output
1

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Two equally good approaches: DFS/BFS from each unvisited node, or Union-Find merging endpoints of every edge.

Hint 2

DFS: walk every node; if unvisited, increment counter and DFS-mark its whole component.

Hint 3

Union-Find: initialize parent[i] = i and components = n. For each edge (a, b), if find(a) != find(b), union them and decrement components. Final components is the answer.

Solution approach

Reveal approach

Two clean approaches. DFS: build an adjacency list from edges; maintain a visited set; iterate i from 0 to n-1, and if i is unvisited, increment counter and run a DFS that marks every reachable node visited. Counter is the answer. Union-Find: initialize parent array as identity and components = n. For each edge (u, v), find the roots of u and v; if they differ, point one root at the other (with union-by-rank or path compression for amortized near-O(1)) and decrement components. Return components. The DSU version is slightly cleaner and scales to streaming-edge variants. Both are O((V + E)·alpha(V)) effectively.

Complexity

Time
O((V + E) * alpha(V))
Space
O(V)

Related patterns

  • union-find
  • dfs
  • bfs
  • graph

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google
  • Meta
  • LinkedIn

Practice these live with InterviewChamp.AI

Drill Number of Connected Components in an Undirected Graph and Graphs problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →