Search⌘ K
AI Features

Number of Connected Components in an Undirected Graph

Number of Connected Components in an Undirected Graph asks you to count the groups of nodes linked by edges, including isolated nodes, in a graph with a given number of nodes.

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

Go
usercode > main.go
package main
func countComponents(n int, edges [][]int) int{
// Replace this placeholder return statement with your code
return -1
}
Number of Connected Components in an Undirected Graph