Search⌘ K
AI Features
Home
Courses
Grokking the Coding Interview Patterns in JavaScript

Number of Connected Components in an Undirected Graph

Understand how to determine the number of connected components in an undirected graph by implementing efficient graph traversal techniques. Explore the use of a union find data structure to optimize your solution with O(E + V) time complexity and apply these skills to solve related coding interview problems confidently.

We'll cover the following...

Statement

For a given integer, n, and an array, edges, return the number of connected components in a graph containing n nodes.

Note: The array edges[i] = [x, y] indicates that there’s an edge between x and y in the graph.

Constraints:

  • 1≤1 \leq n ≤2000 \leq 2000

  • 0≤0 \leq edges.length ≤1000\leq 1000

  • edges[i].length ==2== 2

  • 0≤0 \leq x ,, y <\lt n

  • x ≠\neq y

  • There are no repeated edges.

Examples

canvasAnimation-image
1 / 2

Understand the problem

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

Number of Connected Components in an Undirected Graph

1.

What could be the number of connected components if the following values are given as input?

n = 5

edges = [[0, 1], [3, 4]]

A.

2

B.

3

C.

1

1 / 3

Try it yourself

Implement your solution in main.js in the following coding playground. You will need the provided supporting code to implement your solution.

Note: To solve this problem, you may need to change the implementation of the functions in the given Union Find class.

An optimal solution to this problem runs in O(E + V) time and takes O(V) space.

JavaScript
usercode > main.js
import UnionFind from './union_find.js'



function countComponents(n, edges) {



    // Replace this placeholder return statement with your code

    return -1;

}



export {

    countComponents

}
Number of Connected Components in an Undirected Graph