这道题要求计算无向图中的连通块数量。无向图的连通块指的是一组相互连接的节点,图中的节点如果通过边可以相互到达,就属于同一个连通块。我们需要通过广度优先搜索(BFS)来遍历图,计算图中一共有多少个连通块。
本题和【深度优先搜索2】联通块统计(邻接表存储)思路一样,只是搜索方式不同。
题目描述:
给定一个无向图,该图通过邻接表的方式存储。请你使用广度优先搜索(BFS)算法计算该图的连通块数量。
在无向图中,一个连通块是指图中所有节点之间有路径相连的最大子图。你需要输出图中连通块的数量。
输入:
输出:
输出一个整数,表示图中连通块的数量。
示例:
输入 1:
5 3
1 2
1 3
4 5
输出 1:
2
说明: