#K46752. Connected Components in an Undirected Graph
Connected Components in an Undirected Graph
Connected Components in an Undirected Graph
You are given an undirected graph with n nodes and m edges. The nodes are labeled from 1 to $n$. Each edge connects two distinct nodes. Your task is to compute the number of connected components in the graph.
A connected component is a set of nodes such that there is a path between any two nodes in this set. Formally, if we denote the number of nodes as $n$ and the number of edges as $m$, then you are given $m$ pairs of integers $(u,v)$ indicating that there is an edge between node $u$ and node $v$.
Read the input from standard input (stdin
) and output your answer to standard output (stdout
).
inputFormat
The input is given in the following format:
$n$ $m$ $u_1$ $v_1$ $u_2$ $v_2$ ... $u_m$ $v_m$
Here, $n$ is the number of nodes, $m$ is the number of edges, and each subsequent line contains two integers $u$ and $v$ representing an undirected edge between nodes $u$ and $v$.
outputFormat
Output a single integer which is the number of connected components in the graph.
## sample5 3
1 2
1 3
4 5
2
</p>