102842: [AtCoder]ABC284 C - Count Connected Components

Problem Statement

You are given a simple undirected graph with $N$ vertices numbered $1$ to $N$ and $M$ edges numbered $1$ to $M$. Edge $i$ connects vertex $u_i$ and vertex $v_i$.
Find the number of connected components in this graph.

Notes

A simple undirected graph is a graph that is simple and has undirected edges.
A graph is simple if and only if it has no self-loop or multi-edge.

A subgraph of a graph is a graph formed from some of the vertices and edges of that graph.
A graph is connected if and only if one can travel between every pair of vertices via edges.
A connected component is a connected subgraph that is not part of any larger connected subgraph.

Constraints

• $1 \leq N \leq 100$
• $0 \leq M \leq \frac{N(N - 1)}{2}$
• $1 \leq u_i, v_i \leq N$
• The given graph is simple.
• All values in the input are integers.

Input

The input is given from Standard Input in the following format:

$N$ $M$
$u_1$ $v_1$
$u_2$ $v_2$
$\vdots$
$u_M$ $v_M$

Output

Print the answer.

Sample Input 1

5 3
1 2
1 3
4 5

Sample Output 1

2

The given graph contains the following two connected components:

• a subgraph formed from vertices $1$, $2$, $3$, and edges $1$, $2$;
• a subgraph formed from vertices $4$, $5$, and edge $3$.

Sample Input 2

5 0

Sample Output 2

5

Sample Input 3

4 6
1 2
1 3
1 4
2 3
2 4
3 4

Sample Output 3

1

问题描述

给你一个简单的无向图，图中有N个编号为1到N的顶点和M条编号为1到M的边。第i条边连接顶点u_i和顶点v_i。
找出这个图中的连通分量的个数。

注意

一个简单的无向图是一个既简单又有无向边的图。
一个图是简单的，当且仅当它没有自环或多边。

一个图的子图是通过该图的一些顶点和边形成的图。
一个图是连通的，当且仅当可以通过边在每对顶点之间旅行。
一个连通分量是一个连通子图，它不是任何更大的连通子图的一部分。

约束

• 1≤N≤100
• 0≤M≤N(N−1)2
• 1≤ui,vi≤N
• 给定的图是简单的。
• 输入中的所有值都是整数。

输入

输入通过标准输入以以下格式给出：

N M
u1 v1
u2 v2
vdots
uM vM

输出

打印答案。

样例输入1

5 3
1 2
1 3
4 5

样例输出1

2

给定的图包含以下两个连通分量：

• 由顶点1、2、3和边1、2组成的子图；
• 由顶点4、5和边3组成的子图。

样例输入2

5 0

样例输出2

5

样例输入3

4 6
1 2
1 3
1 4
2 3
2 4
3 4

样例输出3

1