InterviewCrunch

Beta

Number of Connected Components

Medium

Question

Given the number of nodes in an undirected graph and a list of its edges, return the number of connected components in that graph.

For example, n = 3, edges = [[5, 3], [3, 1]] means that there are 3 total nodes, where there's an edge between 5 and 3 as well as an edge between 3 and 1.

You can assume that the value of nodes will range from 0 to num_nodes - 1.

Input: n = 3, edges = [[0, 1], [0, 2]]

Output: 1

All the nodes are connected in some way, therefore there is only one component.Number of Connected Components Example 1

Input: n = 6, edges = [[0, 1], [1, 2], [2, 3], [4, 5]]

Output: 2

There are two components in this case. One containing nodes [0, 1, 2, 3] and the other one containing nodes [4, 5],Number of Connected Components Example 2

Input: n = 8, edges = [[0, 1], [1, 2], [1, 4], [2, 3], [5, 6]]

Output: 3

There are three components in this case. One containing nodes [0, 1, 2, 3, 4], another one containing nodes [5, 6], and the node 7 that's isolated.Number of Connected Components Example 3

Clarify the problem

What are some questions you'd ask an interviewer?

Understand the problem

How many connected components are in the following problem? n = 6, edges = [[0,1], [0, 2], [0, 3], [2, 3], [3, 4]]
1
2
3
4

Login or signup to save your code.

Notes

PrevCoding Pattern: Graph Depth First Search
NextNumber of Islands