171. Number of Connected Components in an Undirected Graph

Medium · Graph

Given an undirected graph represented as an edge list, find the number of connected components.

A connected component is a maximal set of vertices such that there is a path between every pair of vertices in the set. Vertices are numbered from 0 to n-1.

The input provides the number of vertices n and a list of edges where each edge connects two vertices.

Examples

Example 1
Input: n = 5, edges = [[0,1], [1,2], [3,4]]
Output: 2
Explanation: Vertices 0, 1, 2 form one connected component. Vertices 3, 4 form another. Vertex 0 is isolated if not connected to any edge, but here it connects through 0-1-2. So we have 2 components total.
Example 2
Input: n = 4, edges = [[0,1], [2,3]]
Output: 2
Explanation: Component 1: {0, 1}. Component 2: {2, 3}. Total: 2 connected components.

Constraints