题解 | 极大连通图个数连通分量个数等于调用dfs或bfs次数

#include<iostream>
#include<vector>

using namespace std;
vector<string> grid;

void dfs(int x, int y) {
    grid[x][y] = '.';
    for (int dx = -1; dx <= 1; dx++) {
        for (int dy = -1; dy <= 1; dy++) {
            if (dx == 0 && dy == 0) continue;
            int nx = x + dx, ny = y + dy;
            if (nx < 0 || nx >= grid.size() || ny < 0 || ny >= grid[nx].size() ||
                    grid[nx][ny] != 'w') continue;
            dfs(nx, ny);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int h, w;
    cin >> h >> w;
    grid.resize(h);
    for (int i = 0; i < h; i++) cin >> grid[i];
    int ans = 0;
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            if (grid[i][j] == 'w') {
                dfs(i, j);
                ans++;
            }
        }
    }
    cout << ans << endl;
    return 0;
}