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

Number of Connected Components in an Undirected Graph

Explore how to determine the number of connected components in an undirected graph by applying graph traversal and union find algorithms. This lesson helps you understand problem constraints and implement optimized solutions suitable 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.java 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.

Java
usercode > Solution.java
import java.util.*;
class Solution {
    public static int countComponents(int n, int[][] edges) {
        // Replace this placeholder return statement with your code 
        return -1;
    } 
}
Number of Connected Components in an Undirected Graph