Blind 75
Go Back
Number of Connected Components in an Undirected Graph

Problem Statement

Given an undirected graph represented by 'n' nodes labeled from `0` to `n-1` and a list of undirected edges (each edge is a pair of nodes), determine the number of connected components in the graph. A connected component is a group of nodes that are directly or indirectly linked to each other through the edges.

Examples

1. Example 1
• Input: `n = 5`, `edges = [[0,1], [2,3], [3,4]]`
• Expected Output: `2`
• Justification: Two components are: `0-1`, and `2-3-4`.
1. Example 2
• Input: `n = 4`, `edges = [[0,1], [1,2], [2,3]]`
• Expected Output: `1`
• Justification: All the nodes are connected in a single chain: `0-1-2-3`.
1. Example 3
• Input: `n = 3`, `edges = [[0,1]]`
• Expected Output: `2`
• Justification: Two connected components exist: `0-1` and an isolated node `2`.

Constraints:

• `1 <= n <= 2000`
• `1 <= edges.length <= 5000`
• `edges[i].length == 2`
• 0 <= a<sub>i</sub> <= b<sub>i</sub> < n
• a<sub>i</sub> != b<sub>i</sub>
• There are no repeated edges.

Try it yourself

Try solving this question here:

Python3
Python3