欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

连通块问题

程序员文章站 2022-05-30 08:36:08
...

dfs,bfs求连通块
题目
连通块问题
dfs

#include<iostream>
#include<cstdio>
using namespace std;
char c[1100][1100];
int count = 0, f[][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}, {1, 1}, {-1, -1}, {1, -1}, {-1, 1}};
void dfs(int i, int j, int n, int m) {
	if(i<0 || j<0 || i>=n || j>=m || c[i][j] == '.') return ;
	c[i][j] = '.';
	for(int k=0; k<8; k++) {
		dfs(i+f[k][0], j+f[k][1], n, m);
	}
}
int main() {
	count = 0;
	int n, m;
	scanf("%d%d", &n, &m);
	for(int i=0; i<n; i++) {
		for(int j=0; j<m; j++) {
			cin >> c[i][j];
		}
	}
	for(int i=0; i<n; i++) {
		for(int j=0; j<m; j++) {
			if(c[i][j] == 'W') {
				dfs(i, j, n, m);
				count ++;
			}
		}
	}
	printf("%d", count);
	return 0;
}

bfs

#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
char c[110][110];
int f[][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}, {1, 1}, {-1, -1}, {1, -1}, {-1, 1}};
struct pi{
	int x, y;
};
queue<pi> Q;
void bfs(int i, int j, int n, int m) {
	Q.push({i, j});
	c[i][j] = '.';
	while(!Q.empty()) {
		int x = Q.front().x, y = Q.front().y;
		Q.pop();
		for(int k=0; k<8; k++) {
			if(c[x+f[k][0]][y+f[k][1]] == 'W') {
				Q.push({x+f[k][0], y+f[k][1]});
				c[x+f[k][0]][y+f[k][1]] = '.';
			}
		}
	}
}
int main() {
	int count = 0;
	int n, m;
	scanf("%d%d", &n, &m);
	for(int i=0; i<n; i++) {
		for(int j=0; j<m; j++) {
			cin >> c[i][j];
		}
	}
	for(int i=0; i<n; i++) {
		for(int j=0; j<m; j++) {
			if(c[i][j] == 'W') {
				bfs(i, j, n, m);
				count ++;
			}
		}
	}
	printf("%d", count);
	return 0;
}

上面两个很好理解,dfs,bfs每找到一个连通块,就把它给去掉。

并查集也可以求连通块,不过它比较适合邻接表给出的数据。
或者我们把邻接矩阵改成邻接表

相关标签: