Skip to main content
Back to ChallengesNumber of Connected ComponentsEasy 20 min

Number of Connected Components

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

Examples

Input: n = 5, edges = [[0,1],[1,2],[3,4]]
Output: 2
Component {0,1,2} and component {3,4}.
Input: n = 4, edges = []
Output: 4
No edges — every vertex is its own component.

Constraints

  • • 1 <= n <= 2000
  • • 0 <= edges.length <= 5000

Complexity Analysis

Time
O(V + E) with DFS/BFS, or O(E log V) with Union-Find.
Space
O(V) for visited array or Union-Find parent array.

Test Cases

#1 — Two components
Input: n=5 edges=[[0,1],[1,2],[3,4]]
Expected: 2
#2 — All isolated
Input: n=4 edges=[]
Expected: 4
#3 — Fully connected triangle
Input: n=3 edges=[[0,1],[1,2],[0,2]]
Expected: 1

Interactive graph explorer available!

Switch to the Visualize tab to build a custom graph and animate BFS traversal to test your intuition.

Output
Click "Run Code" to see output here...