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**.

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.

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.

#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...