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 Sam K., 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

More Graphs practice problems

See all Graphs problems →