【算法】连通块问题（C/C++）

目录

连通块问题

解决思路

步骤：

初始化：

DFS函数：

复杂度分析

 代码实现（C++）

题目链接：2060. 奶牛选美 - AcWing题库

解题思路：

AC代码： 

题目链接：687. 扫雷 - AcWing题库 

解题思路：

AC代码：

总结：

---

连通块问题

连通块问题（Connected Component Problem）是一个经典的图论问题，通常用来找出图中的所有连通分量。给定一个无向图，连通块问题的目标是确定图中有多少个连通分量（即有多少个互相连通的节点组成的集合）

解决思路

1. 深度优先搜索（DFS） 或 广度优先搜索（BFS）：
   • 可以从任意未访问的节点出发，进行DFS或BFS，标记所有能够访问到的节点，代表这个连通分量。
   • 重复这个过程，直到所有节点都被访问为止。每次从新的未访问节点出发时，就代表发现了一个新的连通分量。
2. 并查集（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);  // 对该节点进行DFSconnected_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]=='*'){//如果此点是雷标记为-1a[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进行图的遍历，寻找有用的信息。文章若有错误、不足的地方恳请大家指出，一起加油。

执笔至此，感触彼多，全文降至、落笔为终，感谢大家的支持。