Number of connected components

Interview

Time limit3sMemory limit512 MB

Summary

Count the connected components of an undirected graph given its vertices and edges.

Level: Easy3 of 10
Topics: Graph, DFS
Solved: No attempts yet

Problem

You are given an undirected graph. Write a program that counts its connected components.

A connected component is a maximal set of vertices that are linked to each other by paths. Any two vertices in the same component have a path between them, and no path joins two vertices in different components. A vertex with no incident edge forms a component by itself.

Input

The first line contains the number of vertices $N$ and the number of edges $M$ , separated by a space. ( $1 \le N \le 1000$ , $0 \le M \le N \times (N-1) / 2$ )

Each of the next $M$ lines contains the two endpoints $u$ and $v$ of an edge. ( $1 \le u, v \le N$ , $u \ne v$ ) The same edge is given only once.

Output

Print the number of connected components on the first line.

Examples4

Example 1
Input
```
6 5
1 2
2 5
5 1
3 4
4 6
```
Expected output
```
2
```
Example 2
Input
```
6 8
1 2
2 5
5 1
3 4
4 6
5 4
2 4
2 3
```
Expected output
```
1
```
Example 3
Input
```
1 0
```
Expected output
```
1
```
Example 4
Input
```
2 1
1 2
```
Expected output
```
1
```