Count Sub-networks in a Network

You are given a network consisting of N devices and M direct connections between them. Two devices are in the same sub-network if they are directly connected or can be connected indirectly through a series of connections. Your task is to determine the number of connected components (sub-networks) in the network.

Formally, if we consider the network as an undirected graph, you need to compute the number of connected components. This can be approached using a breadth-first search (BFS) or depth-first search (DFS) algorithm.

You can express the problem mathematically as follows: Given a graph \(G=(V,E)\) with \(N=|V|\) nodes and a set of edges \(E\) of size \(M\), find the number of connected components \(C\) in \(G\).

Hint: If there are no connections, then each device forms a sub-network on its own, i.e. \(C=N\).

inputFormat

The input is read from stdin and has the following format:

• The first line contains two integers N and M, where N is the number of devices and M is the number of connections.
• The following M lines each contain two integers u and v, representing a direct connection between device u and device v.

outputFormat

Output a single integer to stdout representing the number of sub-networks (connected components) in the network.

5 3
1 2
2 3
4 5

2