代码随想录leetcode200题之图论

1 介绍

本博客用来记录代码随想录leetcode200题之图论相关题目。

2 训练

题目1：98. 所有可达路径

解题思路：有向图，dfs(fa, node)。

C++代码如下，

#include <bits/stdc++.h>using namespace std;int n, m;
unordered_map<int,vector<int>> g;
vector<int> cur;
bool has_path = false;void dfs(int fa, int node) {if (!cur.empty() && cur.back() == n) {has_path = true;for (int i = 0; i+1 < cur.size(); ++i) cout << cur[i] << " ";cout << cur.back() << endl;return;}for (auto x : g[node]) {if (x != fa) {cur.emplace_back(x);dfs(node, x);cur.pop_back();}}return;
}int main() {g.clear();cur.clear();    cin >> n >> m;for (int i = 1; i <= m; ++i) {int a, b;cin >> a >> b;g[a].emplace_back(b);}cur.emplace_back(1);dfs(-1, 1);if (has_path == false) cout << "-1" << endl;return 0;
}

python3代码如下，

import collections has_path = False 
g = collections.defaultdict(list)
cur = []
s = input()
n, m = map(int, s.split())
for i in range(m):s = input()a, b = map(int, s.split())g[a].append(b)def dfs(fa: int, node: int, cur: list) -> None:global has_pathif len(cur) > 0 and cur[-1] == n:newcur = [str(x) for x in cur]res = " ".join(newcur)print(res)has_path = True return for x in g[node]:if x != fa:cur.append(x)dfs(node, x, cur)del cur[-1]returncur.append(1)
dfs(-1, 1, cur)
if has_path == False:print(-1)

题目2：99. 岛屿数量

解题思路：

C++代码如下，

//dfs版本
#include <bits/stdc++.h>using namespace std;const int N = 60;
int n, m;
int g[N][N];
bool st[N][N];void dfs(int i, int j) {if (i < 0 || i >= n || j < 0 || j >= m) return;if (st[i][j]) return;if (g[i][j] == 0) return;st[i][j] = true;dfs(i+1,j);dfs(i-1,j);dfs(i,j+1);dfs(i,j-1);return;
}int main() {cin >> n >> m;for (int i = 0; i < n; ++i) {for (int j = 0; j < m; ++j) {cin >> g[i][j];}}memset(st, 0, sizeof st);int res = 0;for (int i = 0; i < n; ++i) {for (int j = 0; j < m; ++j) {if (g[i][j] == 1 && st[i][j] == false) {dfs(i,j);res += 1;}}}cout << res << endl;return 0;    
}

//bfs版本
#include <bits/stdc++.h>using namespace std;const int N = 60;
int n, m;
int g[N][N];
bool st[N][N];
int dirs[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};void bfs(int i, int j) {queue<pair<int,int>> q;q.push(make_pair(i,j));st[i][j] = true;while (!q.empty()) {auto t = q.front();q.pop();for (int k = 0; k < 4; ++k) {int x = t.first + dirs[k][0];int y = t.second + dirs[k][1];if (x < 0 || x >= n || y < 0 || y >= m) continue;if (st[x][y]) continue;if (g[x][y] == 0) continue;q.push(make_pair(x,y));st[x][y] = true;}}return;
}int main() {cin >> n >> m;for (int i = 0; i < n; ++i) {for (int j = 0; j < m; ++j) {cin >> g[i][j];}}memset(st, 0, sizeof st);int res = 0;for (int i = 0; i < n; ++i) {for (int j = 0; j < m; ++j) {if (g[i][j] == 1 && st[i][j] == false) {bfs(i, j);res += 1;}}}cout << res << endl;return 0;
}

python3代码如下，

#dfs写法
import collections s = input()
n, m = map(int, s.split())
g = [[0] * m for _ in range(n)]
st = [[False] * m for _ in range(n)]
for i in range(n):s = input()s = s.split()s = [int(x) for x in s]for j in range(len(s)):g[i][j] = s[j]def dfs(i: int, j: int) -> None:global n, m, g if i < 0 or i >= n or j < 0 or j >= m:return if st[i][j]:return if g[i][j] == 0:return st[i][j] = True dfs(i+1,j)dfs(i-1,j)dfs(i,j-1)dfs(i,j+1)return res = 0
for i in range(n):for j in range(m):if g[i][j] == 1 and st[i][j] == False:dfs(i,j)res += 1 
print(res)

#bfs写法
import collections s = input()
n, m = map(int, s.split())
g = [[0] * m for _ in range(n)]
st = [[False] * m for _ in range(n)]
for i in range(n):s = input()ls = s.split()for j in range(len(ls)):x = int(ls[j])g[i][j] = x dirs = [[1,0],[-1,0],[0,1],[0,-1]]def bfs(i: int, j: int) -> None:global n, m, g, stq = collections.deque([(i,j)])st[i][j] = True while len(q) > 0:x, y = q.popleft()for k in range(4):nx = x + dirs[k][0]ny = y + dirs[k][1]if nx < 0 or nx >= n or ny < 0 or ny >= m:continue if st[nx][ny]:continue if g[nx][ny] == 0:continue q.append((nx,ny))st[nx][ny] = True return res = 0
for i in range(n):for j in range(m):if g[i][j] == 1 and st[i][j] == False:bfs(i,j)res += 1 
print(res)

题目3：100. 岛屿的最大面积

解题思路：正常bfs和dfs即可。

C++代码如下，

//dfs解法
#include <bits/stdc++.h>using namespace std;const int N = 60;
int n, m;
int g[N][N];
bool st[N][N];
int dirs[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};int dfs(int i, int j) {if (i < 0 || i >= n || j < 0 || j >= m) return 0;if (g[i][j] == 0) return 0;if (st[i][j] == true) return 0;int res = 1;st[i][j] = true;for (int k = 0; k < 4; ++k) {int ni = i + dirs[k][0];int nj = j + dirs[k][1];res += dfs(ni, nj);}return res;
}int main() {cin >> n >> m;for (int i = 0; i < n; ++i) {for (int j = 0; j < m; ++j) {cin >> g[i][j];}}int res = 0;for (int i = 0; i < n; ++i) {for (int j = 0; j < m; ++j) {if (g[i][j] == 1 && st[i][j] == false) {int ans = dfs(i, j);res = max(res, ans);}}}cout << res << endl;return 0;
}

//bfs版本
#include <bits/stdc++.h>using namespace std;const int N = 60;
int n, m;
int g[N][N];
bool st[N][N];
int dirs[4][2] = {{1,0}, {-1,0}, {0,1}, {0,-1}};int bfs(int i, int j) {queue<pair<int,int>> q;q.push(make_pair(i,j));st[i][j] = true;int ans = 1;while (!q.empty()) {auto t = q.front();q.pop();int i = t.first;int j = t.second;for (int k = 0; k < 4; ++k) {int ni = i + dirs[k][0];int nj = j + dirs[k][1];if (ni < 0 || ni >= n || nj < 0 || nj >= m) continue;if (g[ni][nj] == 0) continue;if (st[ni][nj]) continue;q.push(make_pair(ni,nj));st[ni][nj] = true;ans += 1;}}return ans;
}int main() {cin >> n >> m;for (int i = 0; i < n; ++i) {for (int j = 0; j < m; ++j) {cin >> g[i][j];}}memset(st, 0, sizeof st);int res = 0;for (int i = 0; i < n; ++i) {for (int j = 0; j < m; ++j) {if (g[i][j] == 1 && st[i][j] == false) {int ans = bfs(i, j);res = max(res, ans);}}}cout << res << endl;return 0;
}

python3代码如下，

#dfs版本
import collections s = input()
n, m = map(int, s.split())
g = [[0] * m for _ in range(n)]
st = [[False] * m for _ in range(n)]
for i in range(n):s = input()s = s.split()for j in range(len(s)):x = int(s[j])g[i][j] = x 
res = 0
dirs = [[1,0], [-1,0], [0,-1], [0,1]]def dfs(i: int, j: int) -> int:global n, m, g, st if i < 0 or i >= n  or j < 0 or j >= m:return 0if g[i][j] == 0:return 0if st[i][j] == True:return 0res = 1 st[i][j] = True for k in range(4):ni = i + dirs[k][0]nj = j + dirs[k][1]res += dfs(ni, nj)return res 
for i in range(n):for j in range(m):if g[i][j] == 1 and st[i][j] == False:ans = dfs(i,j)res = max(res, ans)
print(res)

#bfs版本
import collections s = input()
n, m = map(int, s.split())
g = [[0] * m for _ in range(n)]
st = [[False] * m for _ in range(n)]
dirs = [[1,0], [-1,0], [0,1], [0,-1]]for i in range(n):s = input()s = s.split()for j in range(len(s)):x = int(s[j])g[i][j] = x def bfs(i: int, j: int) -> int:q = collections.deque([(i,j)])st[i][j] = True ans = 1 while len(q) > 0:i, j = q[0]q.popleft()for k in range(4):ni = i + dirs[k][0]nj = j + dirs[k][1]if ni < 0 or ni >= n or nj < 0 or nj >= m:continue if g[ni][nj] == 0:continue if st[ni][nj]:continue q.append((ni,nj))st[ni][nj] = True ans += 1 return ans res = 0
for i in range(n):for j in range(m):if g[i][j] == 1 and st[i][j] == False:ans = bfs(i,j)res = max(res, ans)
print(res)

题目4：101. 孤岛的总面积

解题思路：

C++代码如下，

//dfs版本
#include <bits/stdc++.h>using namespace std;const int N = 60;
int n, m;
int g[N][N];
int st[N][N];
int dirs[4][2] = {{1,0}, {-1,0}, {0,-1}, {0,1}};int dfs(int i, int j) {if (i < 0 || i >= n || j < 0 || j >= m) return 0;if (st[i][j]) return 0;if (g[i][j] == 0) return 0;int ans = 1;st[i][j] = true;for (int k = 0; k < 4; ++k) {int ni = i + dirs[k][0];int nj = j + dirs[k][1];ans += dfs(ni,nj);}return ans;
}int main() {cin >> n >> m;for (int i = 0; i < n; ++i) {for (int j = 0; j < m; ++j) {cin >> g[i][j];}}memset(st, 0, sizeof st);for (int j = 0; j < m; ++j) {dfs(0,j);dfs(n-1,j);}for (int i = 0; i < n; ++i) {dfs(i,0);dfs(i,m-1);}int res = 0;for (int i = 0; i < n; ++i) {for (int j = 0; j < m; ++j) {if (g[i][j] == 1 && st[i][j] == false) {res += dfs(i,j);}}}cout << res << endl;return 0;
}

//bfs版本
#include <bits/stdc++.h>using namespace std;const int N = 60;
int n, m;
int g[N][N];
int st[N][N];
int dirs[4][2] = {{1,0}, {-1,0}, {0,1}, {0,-1}};int bfs(int i, int j) {if (g[i][j] == 0) return 0;if (st[i][j] == true) return 0;queue<pair<int, int>> q;q.push(make_pair(i,j));st[i][j] = true;int ans = 0;while (!q.empty()) {auto t = q.front();q.pop();ans += 1;for (int k = 0; k < 4; ++k) {int ni = t.first + dirs[k][0];int nj = t.second + dirs[k][1];if (ni < 0 || ni >= n || nj < 0 || nj >= m) continue;if (st[ni][nj]) continue;if (g[ni][nj] == 0) continue;q.push(make_pair(ni,nj));st[ni][nj] = true;}}return ans;
}int main() {cin >> n >> m;for (int i = 0; i < n; ++i) {for (int j = 0; j < m; ++j) {cin >> g[i][j];}}memset(st, 0, sizeof st);for (int i = 0; i < n; ++i) {bfs(i, 0);bfs(i, m-1);}for (int j = 0; j < m; ++j) {bfs(0, j);bfs(n-1, j);}int res = 0;for (int i = 0; i < n; ++i) {for (int j = 0; j < m; ++j) {if (g[i][j] == 1 && st[i][j] == false) {res += bfs(i,j);}}}cout << res << endl;return 0;
}

python3代码如下，

#dfs版本
import collections s = input()
n, m = map(int, s.split())
g = [[0] * m for _ in range(n)]
st = [[False] * m for _ in range(n)]
dirs = [[1,0], [-1,0], [0,1], [0,-1]]for i in range(n):s = input()s = s.split()for j in range(m):x = int(s[j])g[i][j] = x def dfs(i: int, j: int) -> int:global n, m, g, st, dirsif i < 0 or i >= n or j < 0 or j >= m:return 0if g[i][j] == 0:return 0if st[i][j]:return 0ans = 1 st[i][j] = Truefor k in range(4):ni = i + dirs[k][0]nj = j + dirs[k][1]ans += dfs(ni, nj)return ans for i in range(n):dfs(i,0)dfs(i,m-1)
for j in range(m):dfs(0,j)dfs(n-1,j)res = 0
for i in range(n):for j in range(m):if g[i][j] == 1 and st[i][j] == False:res += dfs(i,j)
print(res)

#bfs版本
import collections s = input()
n, m = map(int, s.split())
g = [[0] * m for _ in range(n)]
st = [[False] * m for _ in range(n)]
dirs = [[-1,0], [1,0], [0,-1], [0,1]]for i in range(n):s = input()s = s.split()for j in range(m):g[i][j] = int(s[j])def bfs(i: int, j: int) -> int:global n, m, g, st, dirsif g[i][j] == 0: return 0if st[i][j]:return 0q = collections.deque([(i,j)])st[i][j] = True ans = 0while len(q) > 0:i, j = q.popleft()ans += 1 for k in range(4):ni = i + dirs[k][0]nj = j + dirs[k][1]if ni < 0 or ni >= n or nj < 0 or nj >= m:continue if g[ni][nj] == 0:continue if st[ni][nj]:continue st[ni][nj] = True q.append((ni,nj))return ans for i in range(n):bfs(i, 0)bfs(i, m-1)
for j in range(m):bfs(0, j)bfs(n-1, j)res = 0
for i in range(n):for j in range(m):if g[i][j] == 1 and st[i][j] == False:res += bfs(i,j)
print(res)

题目5：102. 沉没孤岛

解题思路：常规解法。

C++代码如下，

//dfs版本
#include <bits/stdc++.h>using namespace std;const int N = 60;
int n, m;
int g[N][N];
int st[N][N];
int dirs[4][2] = {{1,0}, {-1,0}, {0,-1}, {0,1}};int dfs(int i, int j) {if (i < 0 || i >= n || j < 0 || j >= m) return 0;if (st[i][j]) return 0;if (g[i][j] == 0) return 0;int ans = 1;st[i][j] = true;for (int k = 0; k < 4; ++k) {int ni = i + dirs[k][0];int nj = j + dirs[k][1];ans += dfs(ni,nj);}return ans;
}int main() {cin >> n >> m;for (int i = 0; i < n; ++i) {for (int j = 0; j < m; ++j) {cin >> g[i][j];}}memset(st, 0, sizeof st);for (int j = 0; j < m; ++j) {dfs(0,j);dfs(n-1,j);}for (int i = 0; i < n; ++i) {dfs(i,0);dfs(i,m-1);}for (int i = 0; i < n; ++i) {for (int j = 0; j < m; ++j) {if (g[i][j] == 1 && st[i][j] == false) {cout << 0 << " ";} else {cout << g[i][j] << " ";}}cout << endl;}return 0;
}

//bfs版本
#include <bits/stdc++.h>using namespace std;const int N = 60;
int n, m;
int g[N][N];
int st[N][N];
int dirs[4][2] = {{1,0}, {-1,0}, {0,1}, {0,-1}};int bfs(int i, int j) {if (g[i][j] == 0) return 0;if (st[i][j] == true) return 0;queue<pair<int, int>> q;q.push(make_pair(i,j));st[i][j] = true;int ans = 0;while (!q.empty()) {auto t = q.front();q.pop();ans += 1;for (int k = 0; k < 4; ++k) {int ni = t.first + dirs[k][0];int nj = t.second + dirs[k][1];if (ni < 0 || ni >= n || nj < 0 || nj >= m) continue;if (st[ni][nj]) continue;if (g[ni][nj] == 0) continue;q.push(make_pair(ni,nj));st[ni][nj] = true;}}return ans;
}int main() {cin >> n >> m;for (int i = 0; i < n; ++i) {for (int j = 0; j < m; ++j) {cin >> g[i][j];}}memset(st, 0, sizeof st);for (int i = 0; i < n; ++i) {bfs(i, 0);bfs(i, m-1);}for (int j = 0; j < m; ++j) {bfs(0, j);bfs(n-1, j);}for (int i = 0; i < n; ++i) {for (int j = 0; j < m; ++j) {if (g[i][j] == 1 && st[i][j] == false) {cout << 0 << " ";} else {cout << g[i][j] << " ";}}cout << endl;}return 0;
}

python3代码如下，

#dfs版本
import collections s = input()
n, m = map(int, s.split())
g = [[0] * m for _ in range(n)]
st = [[False] * m for _ in range(n)]
dirs = [[1,0], [-1,0], [0,1], [0,-1]]for i in range(n):s = input()s = s.split()for j in range(m):x = int(s[j])g[i][j] = x def dfs(i: int, j: int) -> int:global n, m, g, st, dirsif i < 0 or i >= n or j < 0 or j >= m:return 0if g[i][j] == 0:return 0if st[i][j]:return 0ans = 1 st[i][j] = Truefor k in range(4):ni = i + dirs[k][0]nj = j + dirs[k][1]ans += dfs(ni, nj)return ans for i in range(n):dfs(i,0)dfs(i,m-1)
for j in range(m):dfs(0,j)dfs(n-1,j)for i in range(n):for j in range(m):if g[i][j] == 1 and st[i][j] == False:g[i][j] = 0
for i in range(n):s = []for j in range(m):s.append(str(g[i][j]))s = " ".join(s)print(s)

#bfs版本
import collections s = input()
n, m = map(int, s.split())
g = [[0] * m for _ in range(n)]
st = [[False] * m for _ in range(n)]
dirs = [[-1,0], [1,0], [0,-1], [0,1]]for i in range(n):s = input()s = s.split()for j in range(m):g[i][j] = int(s[j])def bfs(i: int, j: int) -> int:global n, m, g, st, dirsif g[i][j] == 0: return 0if st[i][j]:return 0q = collections.deque([(i,j)])st[i][j] = True ans = 0while len(q) > 0:i, j = q.popleft()ans += 1 for k in range(4):ni = i + dirs[k][0]nj = j + dirs[k][1]if ni < 0 or ni >= n or nj < 0 or nj >= m:continue if g[ni][nj] == 0:continue if st[ni][nj]:continue st[ni][nj] = True q.append((ni,nj))return ans for i in range(n):bfs(i, 0)bfs(i, m-1)
for j in range(m):bfs(0, j)bfs(n-1, j)for i in range(n):for j in range(m):if g[i][j] == 1 and st[i][j] == False:g[i][j] = 0 
for i in range(n):s = []for j in range(m):s.append(str(g[i][j])) s = " ".join(s)print(s)

题目6：103. 水流问题

解题思路：反向思考，从边界可以到哪些结点。

C++代码如下，

//dfs解法
#include <bits/stdc++.h>using namespace std;const int N = 110;
int n, m;
int g[N][N];
int st1[N][N];
int st2[N][N];
int dirs[4][2] = {{1,0}, {-1,0}, {0,1}, {0,-1}};void dfs(int i, int j, int st[][N]) {st[i][j] = true;for (int k = 0; k < 4; ++k) {int ni = i + dirs[k][0];int nj = j + dirs[k][1];if (ni < 0 || ni >= n || nj < 0 || nj >= m) continue;if (st[ni][nj]) continue;if (g[i][j] > g[ni][nj]) continue;st[ni][nj] = true;dfs(ni,nj,st);}return;
}int main() {cin >> n >> m;for (int i = 0; i < n; ++i) {for (int j = 0; j < m; ++j) {cin >> g[i][j];}}memset(st1, 0, sizeof st1);memset(st2, 0, sizeof st2);for (int j = 0; j < m; ++j) {dfs(0,j,st1);}for (int i = 0; i < n; ++i) {dfs(i,0,st1);}for (int j = 0; j < m; ++j) {dfs(n-1,j,st2);}for (int i = 0; i < n; ++i) {dfs(i,m-1,st2);}for (int i = 0; i < n; ++i) {for (int j = 0; j < m; ++j) {if (st1[i][j] && st2[i][j]) {cout << i << " " << j << endl;}}}return 0;
}

//bfs解法
#include <bits/stdc++.h>using namespace std;const int N = 110;
int n, m;
int g[N][N];
bool st1[N][N];
bool st2[N][N];
int dirs[4][2] = {{-1,0}, {1,0}, {0,-1}, {0,1}};void bfs(int i, int j, bool st[][N]) {queue<pair<int,int>> q;q.push(make_pair(i,j));st[i][j] = true;while (!q.empty()) {auto t = q.front();q.pop();int i = t.first;int j = t.second;for (int k = 0; k < 4; ++k) {int ni = i + dirs[k][0];int nj = j + dirs[k][1];if (ni < 0 || ni >= n || nj < 0 || nj >= m) continue;if (st[ni][nj]) continue;if (g[i][j] > g[ni][nj]) continue;q.push(make_pair(ni,nj));st[ni][nj] = true;}}return;
}int main() {cin >> n >> m;for (int i = 0; i < n; ++i) {for (int j = 0; j < m; ++j) {cin >> g[i][j];}}memset(st1, 0, sizeof st1);memset(st2, 0, sizeof st2);//边界1for (int i = 0; i < n; ++i) {bfs(i,0,st1);}for (int j = 0; j < m; ++j) {bfs(0,j,st1);}//边界2for (int i = 0; i < n; ++i) {bfs(i,m-1,st2);}for (int j = 0; j < m; ++j) {bfs(n-1,j,st2);}for (int i = 0; i < n; ++i) {for (int j = 0; j < m; ++j) {if (st1[i][j] && st2[i][j]) {cout << i << " " << j << endl;}}}return 0;
}

python3代码如下，

#dfs解法
import collections s = input()
n, m = map(int, s.split())
g = [[0] * m for _ in range(n)]
st1 = [[False] * m for _ in range(n)]
st2 = [[False] * m for _ in range(n)]
dirs = [[-1,0], [1,0], [0,-1], [0,1]]for i in range(n):s = input()s = s.split()for j in range(m):x = int(s[j])g[i][j] = x def dfs(i: int, j: int, st: list) -> None:global n, m, g, dirs st[i][j] = True for k in range(4):ni = i + dirs[k][0]nj = j + dirs[k][1]if ni < 0 or ni >= n or nj < 0 or nj >= m:continue if st[ni][nj]:continueif g[i][j] > g[ni][nj]:continuedfs(ni,nj,st)return #边界1
for i in range(n):dfs(i,0,st1)
for j in range(m):dfs(0,j,st1)#边界2
for i in range(n):dfs(i,m-1,st2)
for j in range(m):dfs(n-1,j,st2)for i in range(n):for j in range(m):if st1[i][j] and st2[i][j]:print(f"{i} {j}")

#bfs解法
import collections s = input()
n, m = map(int, s.split())
g = [[0] * m for _ in range(n)]
st1 = [[False] * m for _ in range(n)]
st2 = [[False] * m for _ in range(n)]
dirs = [[-1,0], [1,0], [0,-1], [0,1]]for i in range(n):s = input()s = s.split()for j in range(m):x = int(s[j])g[i][j] = x def bfs(i: int, j: int, st: list) -> None:q = collections.deque([(i,j)])st[i][j] = True while len(q) > 0:i, j = q.popleft()for k in range(4):ni = i + dirs[k][0]nj = j + dirs[k][1]if ni < 0 or ni >= n or nj < 0 or nj >= m:continue if st[ni][nj]:continue if g[i][j] > g[ni][nj]:continue q.append((ni,nj))st[ni][nj] = True return #边界1
for i in range(n):bfs(i,0,st1)
for j in range(m):bfs(0,j,st1)#边界2
for i in range(n):bfs(i,m-1,st2)
for j in range(m):bfs(n-1,j,st2)for i in range(n):for j in range(m):if st1[i][j] and st2[i][j]:print(f"{i} {j}")

题目7：104. 建造最大岛屿

解题思路：给每一个岛屿编号，将属于该岛屿的方块g[i][j]修改为岛屿的值，并且记录岛屿的面积。之后，遍历每一个g[i][j]=0的方块，计算它四邻域的岛屿的面积。

C++代码如下，

//dfs版本
#include <bits/stdc++.h>using namespace std;const int N = 60;
int n, m;
int g[N][N];
bool st[N][N];
unordered_map<int, int> map_mark_size;
int dirs[4][2] = {{-1,0}, {1,0}, {0,-1}, {0,1}};int dfs(int i, int j, int mark) {if (i < 0 || i >= n || j < 0 || j >= m) return 0;if (st[i][j]) return 0;if (g[i][j] == 0) return 0;int ans = 1;st[i][j] = true;g[i][j] = mark;for (int k = 0; k < 4; ++k) {int ni = i + dirs[k][0];int nj = j + dirs[k][1];ans += dfs(ni, nj, mark);}return ans;
}int main() {cin >> n >> m;for (int i = 0; i < n; ++i) {for (int j = 0; j < m; ++j) {cin >> g[i][j];}}memset(st, 0, sizeof st);bool is_all_ones = true;int mark = 2;for (int i = 0; i < n; ++i) {for (int j = 0; j < m; ++j) {if (g[i][j] == 1 && st[i][j] == false) {int cnt = dfs(i,j,mark);map_mark_size[mark] = cnt;mark += 1;}if (g[i][j] == 0) is_all_ones = false; }}if (is_all_ones) { //特判全是1的情况cout << n * m << endl;return 0;}int res = 0;for (int i = 0; i < n; ++i) {for (int j = 0; j < m; ++j) {if (g[i][j] == 0) {set<int> marks;for (int k = 0; k < 4; ++k) {int ni = i + dirs[k][0];int nj = j + dirs[k][1];if (ni < 0 || ni >= n || nj < 0 || nj >= m) continue;marks.insert(g[ni][nj]);}int ans = 1;for (auto mark : marks) {ans += map_mark_size[mark];}res = max(res, ans);}}}cout << res << endl;return 0;
}

//bfs版本
#include <bits/stdc++.h>using namespace std;const int N = 60;
int n, m;
int g[N][N];
bool st[N][N];
int dirs[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
unordered_map<int, int> map_mask_cnt;int bfs(int i, int j, int mask) {queue<pair<int,int>> q;q.push(make_pair(i,j));st[i][j] = true;int ans = 0;while (!q.empty()) {auto t = q.front();int i = t.first;int j = t.second;g[i][j] = mask;ans += 1;q.pop();for (int k = 0; k < 4; ++k) {int ni = i + dirs[k][0];int nj = j + dirs[k][1];if (ni < 0 || ni >= n || nj < 0 || nj >= m) continue;if (g[ni][nj] == 0) continue;if (st[ni][nj]) continue;q.push(make_pair(ni,nj));st[ni][nj] = true;}}return ans;
}int main() {cin >> n >> m;for (int i = 0; i < n; ++i) {for (int j = 0; j < m; ++j) {cin >> g[i][j];}}memset(st, 0, sizeof st);bool is_all_ones = true;int mask = 2;for (int i = 0; i < n; ++i) {for (int j = 0; j < m; ++j) {if (g[i][j] == 1) {int cnt = bfs(i,j,mask);map_mask_cnt[mask] = cnt;mask += 1;}if (g[i][j] == 0) {is_all_ones = false;}}}if (is_all_ones) {cout << n * m << endl;return 0;}int res = 0;for (int i = 0; i < n; ++i) {for (int j = 0; j < m; ++j) {if (g[i][j] == 0) {int ans = 1;set<int> masks;for (int k = 0; k < 4; ++k) {int ni = i + dirs[k][0];int nj = j + dirs[k][1];if (ni < 0 || ni >= n || nj < 0 || nj >= m) continue;masks.insert(g[ni][nj]);}for (auto mask : masks) {ans += map_mask_cnt[mask];}res = max(res, ans);}}}cout << res << endl;return 0;
}

python3代码如下，

#dfs版本
import collections
import sys s = input()
n, m = map(int, s.split())
g = [[0] * m for _ in range(n)]
st = [[False] * m for _ in range(n)]
dirs = [[-1,0], [1,0], [0,-1], [0,1]]
map_mask_cnt = collections.defaultdict(int)for i in range(n):s = input()s = s.split()for j in range(m):x = int(s[j])g[i][j] = x def dfs(i: int, j: int, mask: int) -> int:global n, m, g, st if i < 0 or i >= n or j < 0 or j >= m:return 0if st[i][j]:return 0if g[i][j] == 0:return 0 st[i][j] = True g[i][j] = mask ans = 1 for k in range(4):ni = i + dirs[k][0]nj = j + dirs[k][1]ans += dfs(ni, nj, mask)return ans mask = 2
is_all_ones = True
for i in range(n):for j in range(m):if g[i][j] == 1 and st[i][j] == False:cnt = dfs(i, j, mask)map_mask_cnt[mask] = cntmask += 1 if g[i][j] == 0:is_all_ones = False 
if is_all_ones:print(n * m)sys.exit(0)#print(f"g=\n{g}")
#print(f"map_mask_cnt={map_mask_cnt}")res = 0
for i in range(n):for j in range(m):if g[i][j] == 0:masks = set()for k in range(4):ni = i + dirs[k][0]nj = j + dirs[k][1]if ni < 0 or ni >= n or nj < 0 or nj >= m:continue masks.add(g[ni][nj])ans = 1 #print(f"i={i}, j={j}, masks={masks}")for mask in masks:ans += map_mask_cnt[mask]res = max(res, ans)
print(res)

#bfs版本
import collections 
import sys s = input()
n, m = map(int, s.split())
g = [[0] * m for _ in range(n)]
st = [[False] * m for _ in range(n)]
dirs = [[-1,0],[1,0],[0,-1],[0,1]]
map_mark_cnt = collections.defaultdict(int)for i in range(n):s = input()s = s.split()for j in range(m):x = int(s[j])g[i][j] = x def bfs(i: int, j: int, mask: int) -> int:q = collections.deque([(i,j)])st[i][j] = True g[i][j] = mask ans = 0while len(q) > 0:i, j = q.popleft()ans += 1 for k in range(4):ni = i + dirs[k][0]nj = j + dirs[k][1]if ni < 0 or ni >= n or nj < 0 or nj >= m:continue if st[ni][nj]:continue if g[ni][nj] == 0:continue q.append((ni,nj))st[ni][nj] = True g[ni][nj] = mask return ans mask = 2 
is_all_ones = True 
for i in range(n):for j in range(m):if g[i][j] == 1 and st[i][j] == False:cnt = bfs(i, j, mask)map_mark_cnt[mask] = cnt mask += 1 if g[i][j] == 0:is_all_ones = False 
if is_all_ones:print(n*m)sys.exit(0)res = 0 
for i in range(n):for j in range(m):if g[i][j] == 0:masks = set()for k in range(4):ni = i + dirs[k][0]nj = j + dirs[k][1]if ni < 0 or ni >= n or nj < 0 or nj >= m:continue masks.add(g[ni][nj])ans = 1 for mask in masks:ans += map_mark_cnt[mask]res = max(res, ans) 
print(res)

题目8：110. 字符串接龙

解题思路如下：由于该图中边权相等，因此可以使用bfs来求解最短路。注意理解题意，结点a可以到达结点b的唯一条件是它们只有一处不同，也即abc可以达到abd，但不能到达acb。

C++代码如下，

#include <bits/stdc++.h>using namespace std;bool is_connect(string a, string b) {if (a.size() != b.size()) return false;int cnt = 0;for (int i = 0; i < a.size(); ++i) {if (a[i] != b[i]) cnt++;}return cnt <= 1;
}int main() {int n;set<string> nodes;string snode, enode;cin >> n;cin >> snode >> enode;for (int i = 0; i < n; ++i) {string t;cin >> t;nodes.insert(t);}//把起点和终点也加入nodes变量中nodes.insert(snode);nodes.insert(enode);vector<string> vec_nodes;for (auto x : nodes) {vec_nodes.emplace_back(x);}unordered_map<string, vector<string>> g;for (int i = 0; i < n; ++i) {string a = vec_nodes[i];for (int j = i + 1; j < n; ++j) {string b = vec_nodes[j];if (is_connect(a, b)) {g[a].emplace_back(b);g[b].emplace_back(a);}}}unordered_map<string, int> depth;depth[snode] = 1;queue<string> q;q.push(snode);while (!q.empty()) {auto a = q.front();q.pop();if (a == enode) {break;}for (auto b : g[a]) {if (depth.count(b) == 0) {depth[b] = depth[a] + 1;q.push(b);}}}cout << depth[enode] << endl;return 0;
}

python3代码如下，

import os
import sys 
import collections 
import copy def is_connect(a: str, b: str) -> bool:if len(a) != len(b):return False cnt = 0for i in range(len(a)):if a[i] != b[i]:cnt += 1 return cnt <= 1 if __name__ == "__main__":s = input()n = int(s)s = input()snode,enode = map(str, s.split())nodes = set()for i in range(n):s = input() #input不包含换行符nodes.add(s)nodes.add(snode)nodes.add(enode)nodes = list(nodes)g = collections.defaultdict(list)for i in range(len(nodes)):a = nodes[i]for j in range(i+1,len(nodes)):b = nodes[j]if is_connect(a,b):g[a].append(b)g[b].append(a)q = collections.deque([snode])depth = collections.defaultdict(int)depth[snode] = 1 while len(q) > 0:a = q.popleft()if a == enode:break for b in g[a]:if b not in depth:depth[b] = depth[a] + 1 q.append(b) print(depth[enode])

题目9：105. 有向图的完全可达性

解题思路：遍历图就行了，可以使用bfs来实现，也可以使用dfs来实现。

C++代码：

//dfs解法
#include <bits/stdc++.h>using namespace std;unordered_map<int, vector<int>> g;
vector<bool> st;void dfs(int a) {st[a] = true;for (auto b : g[a]) {if (st[b] == false) {dfs(b);}}return;
}int main() {int n, m;cin >> n >> m;g.clear();for (int i = 0; i < m; ++i) {int a, b;cin >> a >> b;g[a].emplace_back(b); //单向边}st.clear();st = vector<bool>(n+1, false);dfs(1);for (int i = 1; i <= n; ++i) {if (st[i] == false) {cout << "-1" << endl;return 0;}}cout << "1" << endl;return 0;
}

//bfs解法
#include <bits/stdc++.h>using namespace std;int main() {int n, m;cin >> n >> m;unordered_map<int, vector<int>> g;for (int i = 0; i < m; ++i) {int a, b;cin >> a >> b;g[a].emplace_back(b); //单向边}vector<int> st(n+1, false);queue<int> q;q.push(1);st[1] = true;while (!q.empty()) {int a = q.front();q.pop();for (auto b : g[a]) {if (st[b] == false) {st[b] = true;q.push(b);}}}for (int i = 1; i <= n; ++i) {if (st[i] == false) {cout << "-1" << endl;return 0;}}cout << "1" << endl;return 0;
}

python3代码：

#dfs解法
import collectionsif __name__ == "__main__":s = input()n, m = map(int, s.split())g = collections.defaultdict(list)for i in range(m):s = input()a, b = map(int, s.split())g[a].append(b)st = [False] * (n + 1)def dfs(a: int) -> None:global g, st st[a] = True for b in g[a]:if st[b] == False:dfs(b)return dfs(1)res = 1 for i in range(1,n+1):if st[i] == False:res = -1print(res)

#bfs解法
import collectionsif __name__ == "__main__":s = input()n, m = map(int, s.split())g = collections.defaultdict(list)for i in range(m):s = input()a, b = map(int, s.split())g[a].append(b)st = [False] * (n + 1)q = collections.deque([1])st[1] = True while len(q) > 0:a = q.popleft()for b in g[a]:if st[b] == False:st[b] = True q.append(b)res = 1 for i in range(1,n+1):if st[i] == False:res = -1print(res)