连通块问题
连通块问题（Connected Component Problem）是一个经典的图论问题，通常用来找出图中的所有连通分量。给定一个无向图，连通块问题的目标是确定图中有多少个连通分量（即有多少个互相连通的节点组成的集合）。
解决思路
- 深度优先搜索（DFS） 或 广度优先搜索（BFS）：
- 可以从任意未访问的节点出发，进行 DFS 或 BFS，标记所有能够访问到的节点，代表这个连通分量。
- 重复这个过程，直到所有节点都被访问为止。每次从新的未访问节点出发时，就代表发现了一个新的连通分量。
- 并查集（Union-Find）：
- 并查集是一种有效的解决连通性问题的数据结构。可以通过合并节点来动态地找到连通分量。
在这里，我将使用 DFS 的方式解决该问题，并以邻接表的形式来表示图。
步骤
初始化
创建一个访问数组 visited[] 来跟踪每个顶点是否被访问过。
初始化 visited[] 数组，将所有顶点标记为未访问。
DFS 函数
定义一个递归函数 DFS(vertex)，该函数从给定的顶点开始进行深度优先搜索。
在 DFS 函数中：
- 将当前顶点标记为已访问。
- 访问所有与当前顶点相邻的未访问的顶点，并递归调用 DFS。
遍历所有顶点：
- 对于图中的每个未访问的顶点，调用 DFS 函数。
- 记录连通块：每当 DFS 从一个新的未访问的顶点开始时，就表示找到了一个新的连通块。
- 输出结果：可以打印出每个连通块中的顶点，或者计算连通块的数量。
复杂度分析
- 时间复杂度：
O(n + m)，其中n是节点数，m是边数。每个节点和每条边都被遍历一次。 - 空间复杂度：
O(n + m)，用于存储图的邻接表和访问数组。
这种解决方案适用于中小规模的图，如果图的节点数非常大，可以考虑并查集来优化连通性问题。
代码实现（C++）
#include <iostream>
#include <vector>
using namespace std;
const int MAX_N = 1000; // 假设最多 1000 个节点
vector<int> graph[MAX_N]; // 邻接表表示图
bool visited[MAX_N]; // 访问标记数组
// 深度优先搜索（DFS）
void dfs {
visited[node] = ;
( neighbor : graph[node]) {
(!visited[neighbor]) {
(neighbor);
}
}
}
{
n, m;
cin >> n >> m;
( i = ; i < m; i++) {
u, v;
cin >> u >> v;
graph[u].(v);
graph[v].(u);
}
connected_components = ;
( i = ; i <= n; i++) {
(!visited[i]) {
(i);
connected_components++;
}
}
cout << connected_components << endl;
;
}
