连通块（并查集和DFS做法）

390 阅读 0 评论 1 点赞

解题思路一：DFS（深度优先搜索）
```cpp
首先遍历整个方格图，当遇到一个黑色格子时，从该格子开始进行深度优先搜索，并将所有被搜索到的黑色格子涂成白色，表示已经被搜索过了。
在深度优先搜索的过程中，每次遇到一个黑色格子就将其上下左右的黑色格子加入搜索队列。
统计搜索的次数即可得到答案。
```
参考代码：时间复杂度:O(m*n)
```cpp
#include<bits/stdc++.h>
using namespace std;

// 定义常量N，表示方格图的最大边长
const int N = 1010;

int n, m;   // 定义方格图的尺寸n和m
int g[N][N];   // 定义存储方格图的二维数组g

int d[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};  // 定义二维数组d，表示当前方向向上、下、左、右移动的偏移量

// 定义函数dfs，这个函数的功能是从当前位置(x, y)开始进行深度优先搜索，将所有被搜索到的黑色格子涂成白色
void dfs(int x, int y) {
	g[x][y] = 0;   // 将当前位置涂成白色

// 遍历当前位置的四周
	for (int i = 0; i < 4; i ++ ) {
		int a = x + d[i][0], b = y + d[i][1];   // 计算当前方向的位置(a, b)
		// 判断(a, b)是否越界，并且(a, b)是否为黑色格子
		if (a >= 0 && a < n && b >= 0 && b < m && g[a][b]) {
			dfs(a, b);   // 从(a, b)开始进行深度优先搜索
		}
	}
}

int main() {
	cin >> n >> m;  // 输入方格图的尺寸

// 输入方格图的具体内容
	for (int i = 0; i < n; i ++ ) {
		for (int j = 0; j < m; j ++ ) {
			cin >> g[i][j];
		}
	}

int ans = 0;   // 定义变量ans，表示连通块的数量
	// 遍历整个方格图
	for (int i = 0; i < n; i ++ ) {
		for (int j = 0; j < m; j ++ ) {
			if (g[i][j]) { // 当前位置是黑色格子
				ans ++ ; // 连通块数量+1
				dfs(i, j); // 从(i, j)开始进行深度优先搜索，将所有被搜索到的黑色格子涂成白色
			}
		}
	}
	cout << ans << endl;  // 输出连通块的数量

return 0;
}
```

解题思路二：并查集
```cpp
我们可以将每个黑色格子看作一个节点，然后使用并查集来维护节点之间的关系。
首先，我们输入方格图的尺寸和具体内容，然后将每个节点的父节点初始化为其本身。
接下来，我们遍历整个方格图，对于每个黑色格子，我们检查其上、下、左、右四个位置是否也是黑色格子，如果是，则将这两个节点合并到同一个集合中。
最后，我们统计连通块的数量即可得到答案。
注意：在解决这道题时，我们需要注意的一个点是，当前的连通块可能不止包含一个黑色格子，因此我们在遍历方格图时，需要维护每个连通块的边界。
```
参考代码：
```cpp
#include<bits/stdc++.h>
using namespace std;

const int N = 1010;

int n, m;
int g[N][N]; // 存储方格图

int f[N * N]; // 并查集数组

// 并查集的查找函数
int find(int x) {
	if (x != f[x]) f[x] = find(f[x]);
	return f[x];
}

// 并查集的合并函数
void merge(int a, int b) {
	int ra = find(a), rb = find(b);
	if (ra == rb) return;
	f[ra] = rb;
}
int main() {
	cin >> n >> m;

// 输入方格图
	for (int i = 0; i < n; i ++ ) {
		for (int j = 0; j < m; j ++ ) {
			cin >> g[i][j];
		}
	}

// 初始化每个连通块的父节点
	for (int i = 0; i < n * m; i ++ ) f[i] = i;

// 枚举每个位置，如果是黑色格子则检查其上、下、左、右四个位置是否也是黑色格子，如果是则合并
	for (int i = 0; i < n; i ++ ) {
		for (int j = 0; j < m; j ++ ) {
			if (g[i][j]) {
				if (i && g[i - 1][j]) merge(i * m + j, (i - 1) * m + j);
				if (j && g[i][j - 1]) merge(i * m + j, i * m + j - 1);
			}
		}
	}

int ans = 0;
	// 枚举每个位置，如果是黑色格子且是它所在连通块的根节点，则答案加1
	for (int i = 0; i < n; i ++ ) {
		for (int j = 0; j < m; j ++ ) {
			if (g[i][j] && f[i * m + j] == i * m + j) ans ++ ;
		}
	}

cout << ans << endl;

return 0;
}
```

0.0分

2 人评分

本文分类：题解列表
浏览次数：390 次浏览
发布日期：2022-12-21 12:27:03
本文链接：https://blog.dotcpp.com/a/92338

上一篇 > 1112: C语言考试练习题_一元二次方程
下一篇 > 单词查找树c++（结构体+指针）

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：

一点编程也不会写的：零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码？手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

连通块（并查集和DFS做法）

评论列表共有 0 条评论

发表评论取消回复

连通块（并查集和DFS做法）

一笔画问题（dfs）

C++ ： 类和两种访问权限的练习

C++ ： 类和两种访问权限的练习

幸运儿（约瑟夫环-模拟+ Vector）

评论列表 共有 0 条评论

发表评论 取消回复

C++ ：类和两种访问权限的练习

C++ ：类和两种访问权限的练习

评论列表共有 0 条评论

发表评论取消回复