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

Number of Connected Components in an Undirected Graph

Understand how to determine the number of connected components in an undirected graph with n nodes and given edges. Learn to implement and optimize solutions using Union Find, improving your skills in graph algorithms and preparing for coding interviews.

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

Python
usercode > main.py
from union_find import UnionFind





def count_components(n, edges):



    # Replace this placeholder return statement with your code

    return 1
Number of Connected Components in an Undirected Graph