Number of Connected Components

Advanced

Welcome to the world of graph adventures! Today, we're going to explore the concept of connected components in a graph. Imagine a graph as a network of cities with roads connecting them. A connected component is a group of cities that are directly or indirectly connected to each other, and no additional city can be reached to or from a city in the group outside the group.

In this task, you will be given an undirected graph represented by an adjacency list. Your mission, should you choose to accept it, is to determine how many connected components are in the graph.

Example

Suppose you have a graph represented as follows:

{ 0: [1, 2], 1: [0, 2], 2: [0, 1], 3: [], 4: [5], 5: [4] }

This graph can be visualized as having two connected components:

  • Component 1: Nodes 0, 1, and 2 are connected.
  • Component 2: Nodes 4 and 5 are connected.
  • Node 3 is isolated but still counts as a connected component.

So, the function should return 3.

Rules

  • Each node is represented by an integer ID.
  • There are no duplicate or parallel edges.
  • You only need to return the count of connected components.

Function Signature

def number_of_connected_components(graph: dict[int, list[int]]) -> int:

Examples

number_of_connected_components({0: [1], 1: [0], 2: []}) # returns 2 number_of_connected_components({0: [1, 2], 2: [0, 1], 1: [0, 2]}) # returns 1 number_of_connected_components({}) # returns 0

Good luck on your graph treasure hunt, and may you find all the hidden connected components!

Geek
Inputs

Arg 1:

{"0":["1"],"1":["0"],"2":[]}
Expected Output
2
Actual Output
Number of Connected Components [advanced] | Coding for Kids