Grokking the Coding Interview: Patterns for Coding Questions
Ask Author
Back to course home

0% completed

Vote For New Content
Number of Connected Components in an Undirected Graph
Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

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

.....

.....

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible