AT_abc284_c [ABC284C] Count Connected Components

题目描述

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

输入格式

输入以如下格式从标准输入给出。

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

输出格式

请输出答案。

输入输出样例 #1

输入 #1

5 3
1 2
1 3
4 5

输出 #1

2

输入输出样例 #2

输入 #2

5 0

输出 #2

5

输入输出样例 #3

输入 #3

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

输出 #3

1

说明/提示

注释

简单无向图 是指没有自环和重边，且边没有方向的图。
图是简单的，意味着图中不包含自环和多重边。

一个图的子图是指从原图中选择一些顶点和一些边所构成的图。
图是连通的，意味着图中任意两个顶点都可以通过边相互到达。
连通分量是指连通的子图，且不存在包含它的更大的连通子图。

数据范围

• $1 \leq N \leq 100$
• $0 \leq M \leq \frac{N(N-1)}{2}$
• $1 \leq u_i, v_i \leq N$
• 输入保证图为简单图
• 所有输入均为整数

样例解释 1

给定的图包含如下 $2$ 个连通分量：

• 由顶点 $1, 2, 3$ 和边 $1, 2$ 构成的子图
• 由顶点 $4, 5$ 和边 $3$ 构成的子图
  

由 ChatGPT 4.1 翻译