FastPrep
Problem · Graph

Count Connected Components

Learn this problem
● EasyAmazonINTERNNEW GRADPHONE SCREEN
See Amazon hiring insights

Problem statement

You are given an undirected graph with n nodes and a list of edges. Each edge connects two nodes in the graph.

Return the number of connected components in the graph. A connected component is a maximal group of nodes where every pair of nodes is connected by some path.

Function

countConnectedComponents(n: int, edges: int[][]) → int

Complete the function countConnectedComponents in the editor.

countConnectedComponents has the following parameters:

  1. int n: the number of nodes, labeled from 0 to n - 1
  2. int edges[][]: an array where each element [u, v] represents an undirected edge between nodes u and v

Returns

int: the number of connected components in the graph

Examples

Example 1

n = 5edges = [[0, 1], [1, 2], [3, 4]]return = 2
Nodes 0, 1, and 2 form one connected component. Nodes 3 and 4 form another connected component. Therefore, there are 2 connected components.

Example 2

n = 5edges = [[0, 1], [1, 2], [2, 0], [3, 4]]return = 2
The cycle among nodes 0, 1, and 2 is still one connected component. Nodes 3 and 4 form the second component.

Example 3

n = 4edges = []return = 4
With no edges, every node is isolated, so each node is its own connected component.

Constraints

  • Nodes are labeled from 0 to n - 1.
  • The graph is undirected.
  • The input edges are valid node pairs.

More Amazon problems

drafts saved locally
public int countConnectedComponents(int n, int[][] edges) {
  // write your code here
}
n5
edges[[0, 1], [1, 2], [3, 4]]
expected2
checking account