当前位置：首页 > news >正文

力扣hot100——图论

news 2025/7/23 23:17:40

200. 岛屿数量

class Solution {
public:int numIslands(vector<vector<char>>& grid) {int ans = 0;vector<int> dx = { 0, 1, 0, -1 };vector<int> dy = { 1, 0, -1, 0 };int n = grid.size(), m = grid[0].size();vector<vector<int>> vis(n, vector<int>(m, 0));auto dfs = [&](this auto&& dfs, int x, int y) -> void {vis[x][y] = 1;for (int i = 0; i < 4; i++) {int tx = x + dx[i];int ty = y + dy[i];if (tx < 0 || ty < 0 || tx >= n || ty >= m) continue;if (grid[tx][ty] == '0' || vis[tx][ty]) continue;dfs(tx, ty);}};for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (!vis[i][j] && grid[i][j] == '1') {dfs(i, j);ans++;}}}return ans;}
};

dfs求连通块

994. 腐烂的橘子

class Solution {
public:int orangesRotting(vector<vector<int>>& a) {vector<int> dx = { 0, 1, 0, -1 };vector<int> dy = { 1, 0, -1, 0 };int n = a.size(), m = a[0].size();vector<vector<int>> vis(n, vector<int>(m, 0));queue <pair<int, int>> q;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (a[i][j] == 2) q.push({ i, j });}}int ans = 0;while (q.size()) {if (q.size()) ans++;vector<pair<int, int>> v;while (q.size()) {auto [x, y] = q.front();q.pop();vis[x][y] = 1;v.push_back({x, y});}for (auto [x, y] : v) {for (int i = 0; i < 4; i++) {int tx = x + dx[i], ty = y + dy[i];if (tx < 0 || ty < 0 || tx >= n || ty >= m) continue;if (vis[tx][ty] || a[tx][ty] != 1) continue;q.push({tx, ty});}}}for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (a[i][j] == 1 && !vis[i][j]) return -1;}}return max(ans - 1, 0);}
};

bfs

207. 课程表

class Solution {
public:bool canFinish(int n, vector<vector<int>>& a) {vector<vector<int>> e(n);vector<int> deg(n, 0);for (int i = 0; i < a.size(); i++) {int x = a[i][0], y = a[i][1];e[x].push_back(y);deg[y]++;}int cnt = 0;queue<int> q;for (int i = 0; i < n; i++) {if (!deg[i]) q.push(i);}while (q.size()) {auto u = q.front();q.pop();cnt++;for (auto v : e[u]) {deg[v]--;if (!deg[v]) q.push(v);}}return cnt == n;}
};

拓扑排序

208. 实现 Trie (前缀树)

class Trie {
public:int idx;vector<vector<int>> tr;vector<int> cnt;Trie() {idx = 0;tr.resize(1e5, vector<int>(26, 0));cnt.resize(1e5, 0);}void insert(string word) {int p = 0;for (auto ch : word) {int t = ch - 'a';if (!tr[p][t]) tr[p][t] = ++idx;p = tr[p][t];}cnt[p]++;}bool search(string word) {int p = 0;for (auto ch : word) {int t = ch - 'a';if (!tr[p][t]) return false;p = tr[p][t];}return cnt[p];}bool startsWith(string prefix) {int p = 0;for (auto ch : prefix) {int t = ch - 'a';if (!tr[p][t]) return false;p = tr[p][t];}return true;}
};