当前没有测试数据。

C - 计算连通分量

分数：$300$ 分

问题描述

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

说明

简单无向图 是一种没有自环和重边的图。
一个图 简单 当且仅当它没有自环和重边。

一个图的 子图 是由该图的某些顶点和边组成的图。
一个图是 连通图 当且仅当通过边可以从任意两个顶点之间互相到达。
一个连通分量 是一个连通的子图，它不是任何更大的连通子图的一部分。

约束

• $1 \leq N \leq 100$
• $0 \leq M \leq \frac{N(N - 1)}{2}$
• $1 \leq u_i, v_i \leq N$
• 给定的图是简单图。
• 输入中的所有值都是整数。

输入

从标准输入中按以下格式给出：

$N$ $M$

$u_1$ $v_1$

$u_2$ $v_2$

$\vdots$

$u_M$ $v_M$

输出

输出答案。

5 3
1 2
1 3
4 5

2

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

• 子图包含顶点 $1$, $2$, $3$，以及边 $1$, $2$；
• 子图包含顶点 $4$, $5$，以及边 $3$。

5 0

5

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

1