【算法】连通块问题（C/C++）
目录
连通块问题
解决思路
步骤：
初始化：
DFS函数：
复杂度分析
代码实现（C++）
题目链接：2060. 奶牛选美 - AcWing题库
解题思路：
AC代码：
题目链接：687. 扫雷 - AcWing题库
解题思路：
AC代码：
总结：
连通块问题
连通块问题（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 的字符矩阵来表示，如下所示：
................ ..XXXX....XXX... ...XXXX....XX... .XXXX......XXX.. ........XXXXX... .........XXX....其中，X 表示斑点部分。
如果两个 X 在垂直或水平方向上相邻（对角相邻不算在内），则它们属于同一个斑点，由此看出上图中恰好有两个斑点。
约翰牛群里所有的牛都有两个斑点。
约翰希望通过使用油漆给奶牛尽可能少的区域内涂色，将两个斑点合为一个。
在上面的例子中，他只需要给三个 .. 区域内涂色即可（新涂色区域用 ∗∗ 表示）：
................ ..XXXX....XXX... ...XXXX*...XX... .XXXX..**..XXX.. ........XXXXX... .........XXX....请帮助约翰确定，为了使两个斑点合为一个，他需要涂色区域的最少数量。
输入格式
第一行包含两个整数 N 和 M。
接下来 N 行，每行包含一个长度为 M 的由 X 和 .. 构成的字符串，用来表示描述牛皮图案的字符矩阵。
输出格式
输出需要涂色区域的最少数量。
数据范围
1≤N,M≤50
输入样例：
6 16 ................ ..XXXX....XXX... ...XXXX....XX... .XXXX......XXX.. ........XXXXX... .........XXX....输出样例：
3
解题思路：
此题主要是运用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表示第一个点击的单元格）：*..*...**. ....*..... ..c..*.... ........*. ..........被点击的单元格旁边没有地雷，因此当它被打开时显示数字 0，并且它的 8 个相邻单元也被自动打开，此过程不断继续，最终状态如下：
*..*...**. 1112*..... 00012*.... 00001111*. 00000001..此时，仍有不包含地雷的单元格（用
.字符表示）未被打开，因此玩家必须继续点击未打开的单元格，使游戏继续进行。你想尽快赢得游戏胜利并希望找到赢得游戏的最低点击次数。
给定网格的尺寸（N×N），输出能够获胜的最小点击次数。
输入格式
第一行包含整数 T，表示共有 T 组测试数据。
每组数据第一行包含整数 N，表示游戏网格的尺寸大小。
接下来 N 行，每行包含一个长度为 N 的字符串，字符串由
.（无雷）和*（有雷）构成，表示游戏网格的初始状态。输出格式
每组数据输出一个结果，每个结果占一行。
结果表示为
Case #x: y，其中 x 是组别编号（从 1 开始），y 是获胜所需的最小点击次数。数据范围
1≤T≤100
1≤N≤300输入样例：
2 3 ..* ..* **. 5 ..*.. ..*.. .*..* .*... .*...输出样例：
Case #1: 2 Case #2: 8
解题思路：
此题是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进行图的遍历，寻找有用的信息。文章若有错误、不足的地方恳请大家指出，一起加油。
执笔至此，感触彼多，全文降至、落笔为终，感谢大家的支持。