【算法】连通块问题（C/C++）
目录
连通块问题
连通块问题（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(int node) { visited[node] = true; // 标记当前节点已访问 for (int neighbor : graph[node]) { // 遍历所有邻居节点 if (!visited[neighbor]) { dfs(neighbor); // 如果邻居节点未访问，继续DFS } } } int main() { int n, m; // n为节点数，m为边数 cin >> n >> m; // 读取图的边 for (int i = 0; i < m; i++) { int u, v; cin >> u >> v; graph[u].push_back(v); graph[v].push_back(u); // 无向图，双向连接 } int connected_components = 0; // 记录连通块数目 // 遍历所有节点 for (int i = 1; i <= n; i++) { if (!visited[i]) { // 如果节点i未被访问，说明发现了一个新的连通块 dfs(i); // 对该节点进行DFS connected_components++; // 连通块数加1 } } cout << connected_components << endl; return 0; } 题目链接：2060. 奶牛选美 - AcWing题库
听说最近两斑点的奶牛最受欢迎，约翰立即购进了一批两斑点牛。
不幸的是，时尚潮流往往变化很快，当前最受欢迎的牛变成了一斑点牛。
约翰希望通过给每头奶牛涂色，使得它们身上的两个斑点能够合为一个斑点，让它们能够更加时尚。
牛皮可用一个 N×M 的字符矩阵来表示，如下所示：
其中，X 表示斑点部分。
如果两个 X 在垂直或水平方向上相邻（对角相邻不算在内），则它们属于同一个斑点，由此看出上图中恰好有两个斑点。
约翰牛群里所有的牛都有两个斑点。
约翰希望通过使用油漆给奶牛尽可能少的区域内涂色，将两个斑点合为一个。
在上面的例子中，他只需要给三个 .. 区域内涂色即可（新涂色区域用 ∗∗ 表示）：
请帮助约翰确定，为了使两个斑点合为一个，他需要涂色区域的最少数量。
输入格式
第一行包含两个整数 N 和 M。
接下来 N 行，每行包含一个长度为 M 的由 X 和 .. 构成的字符串，用来表示描述牛皮图案的字符矩阵。
输出格式
输出需要涂色区域的最少数量。
数据范围
1≤N,M≤50
输入样例：
输出样例：
解题思路：
此题主要是运用dfs或者bfs去找连通块最小距离。搜索思想，先去找X的点，只要找到了一个X点，那么此点所在的连通块就一网打尽了，把此连通块的点存起来，再搜第二个连通块，把第二个连通块的点也都存起来，然后外循环第一个连通块的点，内循环第二个连通块的点，每次尝试两个点染色，就是图中第一个连通块黄色格子跟第二个连通块黄色格子求距离。在所有里面找一个min的值即可，途中红色的为最小。最后输出减一就是答案，因为这里求的是两点之间点的距离。
AC代码：
#include<iostream> #include<cstring> #include<cmath> #include<vector> #include<climits> using namespace std; typedef pair<int, int> PII; const int N = 55; char s[N][N];//存图 vector<PII> points[2];//连通块 int dx[]={0,0,1,-1};//方向数组 int dy[]={1,-1,0,0}; int n,m; int res=INT_MAX;//无穷大 void dfs(int a,int b,vector<PII>&p){ s[a][b]='.';//走过此连通块的就置为'.'防止重复搜索 p.push_back({a,b});//连通块所有的坐标 for(int i=0;i<4;i++){ int x=a+dx[i]; int y=b+dy[i]; if(x>=0&&y>=0&&x<n&&y<m&&s[x][y]=='X'){//符合条件就继续搜 dfs(x,y,p); } } } int main() { cin>>n>>m; for(int i=0;i<n;i++){ cin>>s[i]; } int k=0; for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ if(s[i][j]=='X'){//找到一个X就能找到此联通块 dfs(i,j,points[k++]); } } } for(auto i:points[0]){//c++11遍历更简单 for(auto j:points[1]){ res=min(res,abs(i.first-j.first)+abs(i.second-j.second));//两个坐标差值 } }//最后要减一，比如(1,1)与(1,3)之间只有一个(1,2)，做差为2，所以要减一 cout<<res-1<<endl; return 0; }题目链接：687. 扫雷 - AcWing题库
扫雷是一种计算机游戏，在 2020 世纪 8080 年代开始流行，并且仍然包含在某些版本的 Microsoft Windows 操作系统中。
在这个问题中，你正在一个矩形网格上玩扫雷游戏。
最初网格内的所有单元格都呈未打开状态。
其中 M 个不同的单元格中隐藏着 M 个地雷。
其他单元格内不包含地雷。
你可以单击任何单元格将其打开。
如果你点击到的单元格中包含一个地雷，那么游戏就会判定失败。
如果你点击到的单元格内不含地雷，则单元格内将显示一个 0 到 8 之间的数字（包括 0 和 8），这对应于该单元格的所有相邻单元格中包含地雷的单元格的数量。
如果两个单元格共享一个角或边，则它们是相邻单元格。
另外，如果某个单元格被打开时显示数字 0，那么它的所有相邻单元格也会以递归方式自动打开。
当所有不含地雷的单元格都被打开时，游戏就会判定胜利。
例如，网格的初始状态可能如下所示（*表示地雷，而c表示第一个点击的单元格）：
被点击的单元格旁边没有地雷，因此当它被打开时显示数字 0，并且它的 8 个相邻单元也被自动打开，此过程不断继续，最终状态如下：
此时，仍有不包含地雷的单元格（用.字符表示）未被打开，因此玩家必须继续点击未打开的单元格，使游戏继续进行。
你想尽快赢得游戏胜利并希望找到赢得游戏的最低点击次数。
给定网格的尺寸（N×N），输出能够获胜的最小点击次数。
输入格式
第一行包含整数 T，表示共有 T 组测试数据。
每组数据第一行包含整数 N，表示游戏网格的尺寸大小。
接下来 N 行，每行包含一个长度为 N 的字符串，字符串由.（无雷）和*（有雷）构成，表示游戏网格的初始状态。
输出格式
每组数据输出一个结果，每个结果占一行。
结果表示为Case #x: y，其中 x 是组别编号（从 1 开始），y 是获胜所需的最小点击次数。
数据范围
1≤T≤100
1≤N≤300
输入样例：
输出样例：
解题思路：
此题是DFS求连通块，扫雷中分三种情况，如果你点一次，此点附近没有雷，那么这一个0连通块就会全部显示出来，此0连通块边界就会显示此点附近雷的个数。第二种就是不在0连通块，附近有雷的点，为了要赢，这个也必须要点。第三种就是在连通块里面，附近有雷的点，这个点对于此题来说，先点了第一种，那么第三种的点也被包含在里面了，省了一步，此题要求最少点多少次，那么答案就是0连通块的数量+不在0连通块，附近有雷的点（1--8）。此题可用DFS、BFS进行找0联通块。
视频讲解：AcWing 687. 扫雷（每日一题）_哔哩哔哩_bilibili
AC代码：
#include<iostream> using namespace std; const int N=305; int n,T; char str[N][N]; int a[N][N];//标记(i,j)点附近有几个雷 void dfs(int x,int y){ int t=a[x][y]; a[x][y]=-1; if(t){ return; } for(int i=x-1;i<=x+1;i++){ for(int j=y-1;j<=y+1;j++){ if(i>=0&&j>=0&&i<n&&j<n&&a[i][j]!=-1){ dfs(i,j); } } } } int main(){ cin>>T; for(int k=1;k<=T;k++){ cin>>n; for(int j=0;j<n;j++){ cin>>str[j]; } int res=0; for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ if(str[i][j]=='*'){//如果此点是雷标记为-1 a[i][j]=-1; }else{ a[i][j]=0; for(int l=i-1;l<=i+1;l++){ for(int r=j-1;r<=j+1;r++){ if(str[l][r]=='*'&&l>=0&&r>=0&&l<n&&r<n){//附近是雷且没有越界 a[i][j]++; } } } } } } for(int i=0;i<n;i++){//求为0的连通块 for(int j=0;j<n;j++){ if(a[i][j]==0){ res++; dfs(i,j); } } } for(int i=0;i<n;i++){//求不属于0连通块且不是雷的点 for(int j=0;j<n;j++){ if(a[i][j]!=-1){ res++; } } } cout<<"Case #"<<k<<":"<<res<<endl; } return 0; }总结：
此题思路难想，当思路打开了，按照板子就可以写出来，需要多练习问题转化能力，如此题转化为连通块最小距离。用dfs或者bfs进行图的遍历，寻找有用的信息。文章若有错误、不足的地方恳请大家指出，一起加油。
执笔至此，感触彼多，全文降至、落笔为终，感谢大家的支持。
