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

Number of Connected Components in an Undirected Graph

Explore methods to determine the number of connected components in an undirected graph with n nodes and edges. Understand the problem constraints and implement an efficient solution using data structures like Union Find, achieving optimal time and space complexity.

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