FastPrep
Problem · Graph

Count Connected Components

● EasyAmazonINTERNNEW GRADPHONE SCREEN
See Amazon hiring insights

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 Description

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
01 · Example 1
n = 5
edges = [[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.
02 · Example 2
n = 5
edges = [[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.
03 · Example 3
n = 4
edges = []
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
sign in to submit