#K37852. Connected Components in a Network
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.
## sample1 0
1