Count Connected Components

题目描述

你被给定了一个顶点编号为 $1$ 到 $N$ 的简单无向图和编号为 $1$ 到 $M$ 的边。边 $i$ 连接顶点 $u_i$ 和顶点 $v_i$。
求该图中的连通分量个数。

输入格式

输入按下述格式从标准输入提供： $N$ $M$ $u_1$ $v_1$ $u_2$ $v_2$ $\vdots$ $u_M$ $v_M$

输出格式

输出答案。

5 3
1 2
1 3
4 5

2

5 0

5

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

1

提示

$1 \leq N \leq 100$ $0 \leq M \leq \frac{N(N - 1)}{2}$ $1 \leq u_i, v_i \leq N$ 给定的图是简单图。 输入中的所有值都是整数。A simple undirected graph 是一个既是 simple 又具有无向边的图。
一个图是 simple 当且仅当它没有自环或重边。 一个 subgraph 是由原图的一些顶点和边构成的图。
一个图是 connected 当且仅当可以通过边在任意一对顶点之间旅行。 一个 connected component 是一个连通子图，且不属于任何更大的连通子图。给定的图包含以下两个连通分量：

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

标签: AtCoder|abc284C

来源

AtCoder|abc284C