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

Number of Connected Components in an Undirected Graph

Explore how to determine the number of connected components in an undirected graph with n nodes. This lesson guides you to implement an efficient union find solution in Go, helping you improve problem-solving skills for graph-related coding interviews by analyzing edges and optimizing runtime.

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