#K37852. Connected Components in a Network

    ID: 26068 Type: Default 1000ms 256MiB

Connected Components in a Network

Connected Components in a Network

In this problem, you are given an undirected graph representing a network of computers. The graph has n vertices (computers) and m edges (network cables), where each edge connects two computers directly.

Your task is to compute the number of connected components in the network. A connected component is a set of computers in which any computer can reach any other computer through a series of direct connections.

Formally, given n and m along with m edges, you are to calculate the number of connected components. This can be mathematically represented as follows:

$$\text{components} = \text{number of equivalence classes in }\{1, 2, \dots, n\} $$

where two computers belong to the same equivalence class if there exists a path connecting them.

inputFormat

The input is given via stdin and has the following format:

 n m
 u1 v1
 u2 v2
 ...
 um vm

Here:

  • n: An integer representing the number of computers (vertices). (1 ≤ n ≤ 10^5, for example)
  • m: An integer representing the number of network cables (edges).
  • ui vi: Each of the following m lines contains two integers that indicate a direct connection between computer ui and computer vi.

outputFormat

Output the number of connected components in the network. The result should be printed to stdout as a single integer.

## sample
1 0
1