Design Gurus Logo
Blind 75
Number of Connected Components in an Undirected Graph (medium)

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]]
Image
  • 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]]
Image
  • 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]]
Image
  • 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