【广度优先搜索3】联通块问题

题面描述

这道题要求计算无向图中的连通块数量。无向图的连通块指的是一组相互连接的节点，图中的节点如果通过边可以相互到达，就属于同一个连通块。我们需要通过广度优先搜索（BFS）来遍历图，计算图中一共有多少个连通块。

题解

本题和【深度优先搜索2】联通块统计（邻接表存储）思路一样，只是搜索方式不同。

题目描述：

给定一个无向图，该图通过邻接表的方式存储。请你使用广度优先搜索（BFS）算法计算该图的连通块数量。

在无向图中，一个连通块是指图中所有节点之间有路径相连的最大子图。你需要输出图中连通块的数量。

输入：

• 第一行包含两个整数 $n$ 和 $m$（$2 \leq n \leq 10^4$，$1 \leq m \leq 10^5$），表示图中有 $n$ 个节点和 $m$ 条边。
• 接下来的 $m$ 行，每行包含两个整数 $u$ 和 $v$（$1 \leq u, v \leq n$），表示存在一条从节点 $u$ 到节点 $v$ 的无向边。

输出：

输出一个整数，表示图中连通块的数量。

示例：

输入样例

5 3
1 2
1 3
4 5

输出样例

2

说明：

• 在示例 1 中，图中有两个连通块：一个包含节点 $1$、$2$、$3$，另一个包含节点 $4$ 和 $5$。