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

Number of Connected Components in an Undirected Graph

Explore how to determine the number of connected components in an undirected graph with n nodes and a list of edges. Practice implementing graph traversal or Union-Find techniques in C++ to solve the problem efficiently within given constraints.

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

C++
usercode > Solution.cpp
#include "UnionFind.cpp"
int CountComponents(int n, vector<vector<int>> edges){
    // Replace this placeholder return statement with your code
    return 1;
}
Number of Connected Components in an Undirected Graph