City Clusters

Problem Statement: Given a city with \(n\) zones and a list of \(m\) bidirectional roads connecting them, determine the number of clusters (i.e. connected components) in the city. A cluster is defined as a group of zones where each zone can reach any other zone in the same cluster via the given roads. If a zone has no connecting road, it is considered its own cluster.

Mathematical Formulation: Consider an undirected graph with vertices \(\{1,2,\dots,n\}\) and a set of edges represented by pairs \((u,v)\). The goal is to find the number of connected components in this graph. In other words, if \(C\) is the set of connected components, compute \(|C|\).

inputFormat

Input Format:

• The first line contains two integers \(n\) and \(m\), where \(n\) is the number of zones and \(m\) is the number of roads.
• The next \(m\) lines each contain two integers \(u\) and \(v\), indicating that there is a bidirectional road between zone \(u\) and zone \(v\).

outputFormat

Output Format:

• Output a single integer representing the number of clusters in the city.

6 5
1 2
2 3
4 5
4 6
5 6

2