#K53427. Counting Connected Components

    ID: 29529 Type: Default 1000ms 256MiB

Counting Connected Components

Counting Connected Components

Given an undirected graph with \( n \) nodes and \( m \) edges, your task is to determine the number of connected components in the graph.

A connected component is a set of nodes where every pair of nodes is connected via a path. In a graph with no edges, each node is an isolated connected component. For example, if \( n = 5 \) and the edges are \( (1, 2) \), \( (2, 3) \), and \( (4, 5) \), then the graph consists of two connected components: one containing \( \{1, 2, 3\} \) and another containing \( \{4, 5\} \).

inputFormat

The first line of input contains two integers \( n \) and \( m \) \((1 \le n \le 10^5, 0 \le m \le 10^5)\), representing the number of nodes and edges, respectively.

The next \( m \) lines each contain two integers \( u \) and \( v \) \((1 \le u, v \le n, u \neq v)\), which denote an undirected edge between nodes \( u \) and \( v \). There are no duplicate edges in the input.

outputFormat

Output a single integer that represents the number of connected components in the graph.

## sample
5 3
1 2
2 3
4 5
2

</p>