连通分量计数

题目描述

给定一个无向图，计算图中的连通分量个数。

连通分量是指图中任意两个顶点之间都存在路径连接的极大连通子图。

输入

第一行包含两个整数 n, m，分别表示图的顶点数和边数。
接下来 m 行，每行包含两个整数 u, v，表示顶点 u 和顶点 v 之间有一条无向边。

输出

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

样例

提示

样例1解释

图中有6个顶点，4条边，形成两个连通分量：

• 连通分量1：顶点1, 2, 3（通过边1-2, 2-3连接）

• 连通分量2：顶点4, 5, 6（通过边4-5, 5-6连接）
  因此连通分量个数为2。

数据范围

• 1 ≤ n ≤ 1000

• 0 ≤ m ≤ n × (n - 1) / 2

• 1 ≤ u, v ≤ n

• 保证图是简单无向图（无自环，无重边）

算法说明

连通分量计数原理

1. 初始化：所有顶点标记为未访问

2. 遍历顶点：对于每个未访问的顶点：

   • 增加连通分量计数

   • 使用DFS或BFS遍历该顶点所在连通分量中的所有顶点

3. 统计结果：最终的计数即为连通分量个数

关键特性

• 访问标记：确保每个顶点只被访问一次

• 完整遍历：必须检查所有顶点，包括孤立顶点

• 图遍历：使用DFS或BFS探索连通区域

时间复杂度

• 构建图：O(m)

• 遍历图：O(n + m)

• 总复杂度：O(n + m)

空间复杂度

• 图存储：O(n + m)

• 访问数组：O(n)

• DFS栈/BFS队列：O(n)

应用场景

1. 网络连通性：检查计算机网络中的连通状况

2. 社交网络：分析社交网络中的群体划分

3. 图像处理：识别图像中的连通区域

4. 地图导航：确定地图上的连通区域

注意事项

1. 孤立顶点：单个顶点也是一个连通分量

2. 无向图：算法针对无向图设计

3. 顶点编号：题目中顶点编号从1开始

4. 边界情况：注意n=0或m=0的情况

扩展思考

1. 如何输出每个连通分量包含的顶点？

2. 如何判断图是否是连通图？

3. 在有向图中如何计算强连通分量？

4. 如何找到最大的连通分量？

提交人

来源/分类