# Problem B

Staying Connected

An undirected, unweighted graph $G$ is specified by a set of vertices $V$ and a set of edges $E$, where each edge connects two vertices (and, thus, is specified by a pair of vertices). For example, take this graph:

This graph is defined as $V=\{ 0,1,2,3,4\} $ and $E=\{ (0,1),(0,3),(0,4),(1,4),(2,3),(3,4)\} $. Note that there is a single pair of vertices per edge (i.e., since this is an undirected graph, we do not need to include both $(0,1)$ and $(1,0)$ in $E$; just one is enough to specify that there exists an edge between vertex 0 and vertex 1).

In the above graph, all the vertices are *connected*.
i.e., for all possible pairs of vertices $(v_1, v_2)$ in the graph, it is
possible to find a path from $v_1$ to $v_2$ (e.g., vertex $0$ and vertex $2$ are not directly connected with an
edge, but you can reach vertex $2$ from vertex $0$ by going through vertex
$3$). Here is an example
of a graph where all the vertices are *not*
connected:

This graph is defined as $V=\{
0,1,2,3,4\} $ and $E=\{
(0,1), (0,2), (1,2), (3,4)\} $. Note that this does not
specify two graphs, but rather a single graph with two
*connected components*. A connected component is a
subgraph $G’$ of a graph
$G$ such that, for every
possible pair of vertices in $G’$, there exists a path between
those vertices *and* there are no paths in $G$ that connect the vertices in
$G’$ to any of the other
vertices in $G$. So, the
two connected components in the above graph are $V_1=\{ 0,1,2\} $ and $V_2=\{ 3,4\} $.

As a counterexample, vertices $\{ 0,1\} $ would not be a connected component because, although there does exists a path between all possible pairs of vertices (in this case, just $0$ and $1$), the graph also contains paths connecting $0$ and $1$ to other vertices in the graph.

You will write a program that, given the specification of a
graph $G$, will count the
number of connected components in that graph. An easy way of
doing this is by using *depth-first search*:

function dfs(graph, root_vertex) Mark root_vertex as "visited" for each vertex v connected to root_vertex by an edge do if v is not marked as "visited" Mark v as "visited" dfs(graph, v) end if end for end function

Take into account that depth-first search does *not*
solve the problem entirely. However, doing a depth-first search
starting at a vertex in a connected component will result in
all the vertices in that connected component being marked as
“visited”. This is a useful stepping stone towards figuring out
the number of connected components.

## Input

The input contains the specification of a single graph $G$. The first two lines contain the number of vertices $|V|$ ($1 \leqslant |V| \leqslant 200$) and the number of edges $|E|$ ($0 \leqslant |E| \leqslant \frac{|V|\cdot (|V|-1)}{2}$). The input is followed by $|E|$ lines, each containing a pair of integers separated by a single space. This pair of integers specifies the vertices connected by that edge. We assume that vertices are numbered from 0 (so, if $|V|=4$ then $V=\{ 0,1,2,3\} $).

Note that the two sample inputs correspond to the two example graphs shown above.

## Output

You must print a single integer: the number of connected components in $G$.

Sample Input 1 | Sample Output 1 |
---|---|

5 6 0 1 0 3 0 4 1 4 2 3 3 4 |
1 |

Sample Input 2 | Sample Output 2 |
---|---|

5 4 0 1 0 2 1 2 3 4 |
2 |