使用DFS遍历计算无向图连通分量的数量

"本文介绍如何计算无向图的连通子图个数，采用深度优先搜索（DFS）算法实现。" 在计算机科学中，图是一种数据结构，用于表示对象之间的关系。无向图是其中的一种，其中每条边连接两个顶点，没有方向之分。连通子图是指图中的一个子集，其中任意两个顶点之间都存在路径。计算无向图的连通子图个数是一个常见的图论问题，特别是在网络分析、社交网络等领域。 在给定的代码中，使用了C++语言进行实现，主要涉及以下几个关键点： 1. **邻接表**：`vector<int> G[maxn]` 用于存储图的邻接表，每个元素`G[v]`是一个整数向量，表示与顶点`v`相连的所有顶点。 2. **访问标记**：`bool vis[maxn] = {false}` 用于记录每个顶点是否已被访问过，避免在DFS过程中重复访问。 3. **深度优先搜索**（DFS）函数`dfs(int v)`： - 首先将当前顶点`v`标记为已访问。 - 然后遍历与`v`相邻的所有顶点，如果某个顶点未被访问，则对其调用DFS。 4. **主程序**： - 首先读取图的节点数`n`和边的信息，构建邻接表。 - 初始化所有顶点为未访问状态。 - 使用一个变量`block`记录连通子图的个数，初始值为0。 - 枚举所有顶点，对于每个未访问过的顶点，调用DFS进行遍历，并将`block`加一，表示找到了一个新的连通子图。 5. **输入输出**： - 输入示例给出了两个测试案例，每个案例包含图的节点数`n`以及边的连接信息。 - 输出结果是连通子图的个数。 例如，对于第一个输入案例： ``` Input: 5 1 2 1 3 1 4 2 5 ``` 图由节点1、2、3、4、5组成，其中1与2、3、4相连，2与5相连。整个图是连通的，所以输出结果是1。 第二个输入案例： ``` Input: 5 1 3 1 4 2 5 3 4 ``` 图中有两个连通子图：{1, 3, 4} 和 {2, 5}，因此输出结果是2。 通过这个算法，我们可以有效地找出无向图中的所有连通子图，并计算其数量。这种方法适用于节点数和边数相对较小的问题，对于大规模图可能需要更高效的算法，如并查集或Tarjan算法等。