代码随想录--第一天图论---岛屿的数量

99 统计岛屿的数量 c++

99. 岛屿数量

#include <iostream> #include <vector> #include <queue> using namespace std; struct MGraph { int numVertices, numEdges; vector<vector<int>> Edge; }; int dir[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}}; void dfs(MGraph& mGraph, vector<vector<bool>>& visited, int x, int y) { for (int i = 0; i < 4; ++i) { int nextx = x + dir[i][0]; int nexty = y + dir[i][1]; if (nextx >= 0 && nextx < mGraph.Edge.size() && nexty >= 0 && nexty < mGraph.Edge[0].size() && !visited[nextx][nexty] && mGraph.Edge[nextx][nexty] == 1) { visited[nextx][nexty] = true; dfs(mGraph, visited, nextx, nexty); } } } void bfs(MGraph& mGraph, vector<vector<bool>>& visited, int x, int y) { queue<pair<int, int>> q; visited[x][y] = true; q.push({x, y}); while (!q.empty()) { auto [curx, cury] = q.front(); q.pop(); for (int i = 0; i < 4; ++i) { int nextx = curx + dir[i][0]; int nexty = cury + dir[i][1]; if (nextx >= 0 && nextx < mGraph.Edge.size() && nexty >= 0 && nexty < mGraph.Edge[0].size() && !visited[nextx][nexty] && mGraph.Edge[nextx][nexty] == 1) { visited[nextx][nexty] = true; q.push({nextx, nexty}); } } } } int main() { int M, N; cin >> M >> N; MGraph mGraph; mGraph.Edge.resize(M, vector<int>(N)); for (int i = 0; i < M; ++i) { for (int j = 0; j < N; ++j) { cin >> mGraph.Edge[i][j]; } } vector<vector<bool>> visited(M, vector<bool>(N, false)); int result = 0; for (int i = 0; i < M; ++i) { for (int j = 0; j < N; ++j) { if (!visited[i][j] && mGraph.Edge[i][j] == 1) { result++; dfs(mGraph, visited, i, j); // 可以替换为 bfs 如果需要广度优先搜索 } } } cout << result << endl; return 0; } 补充题目 蓝桥杯 -- 危险系数

P8604 [蓝桥杯 2013 国 C] 危险系数 - 洛谷