- About
- Contact Us
- Privacy
- Terms of Service
- Copyright Complaint
- Language
- Legacy mode
- Theme
- 京ICP备2025123107号-1
- Worker 0, 140ms
- Powered by Hydro v4.18.0 Community
题目描述：
给定一个无向图，该图通过邻接表的方式存储。请你使用广度优先搜索（BFS）算法计算该图的连通块数量。
在无向图中，一个连通块是指图中所有节点之间有路径相连的最大子图。你需要输出图中连通块的数量。
输入：
输出：
输出一个整数，表示图中连通块的数量。
示例：
输入 1：
5 3
1 2
1 3
4 5
输出 1：
2
说明：
这道题要求计算无向图中的连通块数量。无向图的连通块指的是一组相互连接的节点，图中的节点如果通过边可以相互到达，就属于同一个连通块。我们需要通过广度优先搜索（BFS）来遍历图，计算图中一共有多少个连通块。
本题和【深度优先搜索2】联通块统计（邻接表存储）思路一样，只是搜索方式不同。
以下是详细的解题思路，并配有对应的Python代码实现：
代码示例：
from collections import deque
# 全局邻接表，假设节点编号从1到10000
adj = [[] for _ in range(10001)]
visited = [False] * 10001 # 访问标记列表
解释：
adj 是一个包含10001个子列表的列表，用于存储每个节点的邻接节点。visited 是一个布尔列表，用于标记每个节点是否已经被访问过，初始化为全False。bfs(start)，从起始节点 start 开始遍历，标记所有可达节点为已访问。代码示例：
def bfs(start):
queue = deque()
queue.append(start)
visited[start] = True # 标记起始节点为已访问
while queue:
node = queue.popleft()
# 遍历所有相邻节点
for neighbor in adj[node]:
if not visited[neighbor]:
visited[neighbor] = True # 标记为已访问
queue.append(neighbor) # 加入队列继续遍历
解释：
deque 作为队列来实现BFS，提高出队和入队操作的效率。visited[start] = True 标记起始节点为已访问，防止重复遍历。代码示例：
count = 0 # 连通块数量
# 遍历所有节点，进行BFS
for i in range(1, n + 1):
if not visited[i]:
bfs(i)
count += 1 # 每找到一个连通块，计数加1
print(count) # 输出连通块的数量
解释：
bfs(i) 并增加计数。将上述步骤汇总，得到以下完整的Python代码实现：
from collections import deque
# 全局邻接表，假设节点编号从1到10000
adj = [[] for _ in range(10001)]
visited = [False] * 10001 # 访问标记列表
def bfs(start):
queue = deque()
queue.append(start)
visited[start] = True # 标记起始节点为已访问
while queue:
node = queue.popleft()
# 遍历所有相邻节点
for neighbor in adj[node]:
if not visited[neighbor]:
visited[neighbor] = True # 标记为已访问
queue.append(neighbor) # 加入队列继续遍历
def main():
import sys
input = sys.stdin.readline # 使用readline提高输入效率
n, m = map(int, input().split()) # 读取节点数和边数
# 读取边的信息并构建邻接表
for _ in range(m):
u, v = map(int, input().split())
adj[u].append(v)
adj[v].append(u) # 无向图双向连接
count = 0 # 连通块数量
# 遍历所有节点，进行BFS
for i in range(1, n + 1):
if not visited[i]:
bfs(i)
count += 1 # 每找到一个连通块，计数加1
print(count) # 输出连通块的数量
if __name__ == "__main__":
main()