代码随想录leetcode200题之图论

1 介绍

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

2 训练

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

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

C++代码如下，

#include 

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_path
    if 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]
    return

cur.append(1)
dfs(-1, 1, cur)
if has_path == False:
    print(-1)

题目2：99. 岛屿数量

解题思路：

C++代码如下，

//dfs版本
#include 

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 

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, st
    q = 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 

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 

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 0
    if g[i][j] == 0:
        return 0
    if st[i][j] == True:
        return 0
    res = 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 

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 

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, dirs
    if i < 0 or i >= n or j < 0 or j >= m:
        return 0
    if g[i][j] == 0:
        return 0
    if st[i][j]:
        return 0
    ans = 1 
    st[i][j] = True
    for 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, dirs
    if g[i][j] == 0: 
        return 0
    if st[i][j]:
        return 0

    q = collections.deque([(i,j)])
    st[i][j] = True 

    ans = 0

    while 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 

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 

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, dirs
    if i < 0 or i >= n or j < 0 or j >= m:
        return 0
    if g[i][j] == 0:
        return 0
    if st[i][j]:
        return 0
    ans = 1 
    st[i][j] = True
    for 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, dirs
    if g[i][j] == 0: 
        return 0
    if st[i][j]:
        return 0

    q = collections.deque([(i,j)])
    st[i][j] = True 

    ans = 0

    while 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 

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 

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);

    //边界1
    for (int i = 0; i < n; ++i) {
        bfs(i,0,st1);
    }
    for (int j = 0; j < m; ++j) {
        bfs(0,j,st1);
    }

    //边界2
    for (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]:
            continue
        if g[i][j] > g[ni][nj]:
            continue
        dfs(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 

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 

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 0
    if st[i][j]:
        return 0
    if 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] = cnt
            mask += 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 = 0

    while 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 

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 = 0
    for 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 

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 

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 collections

if __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 = -1

    print(res)

#bfs解法
import collections

if __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 = -1

    print(res)

题目10：106. 岛屿的周长

解题思路：遍历每一个值为1的小方块，然后遍历它的四邻域，如果是0的话，则res += 1，最终返回res。

C++代码如下，

#include 

using namespace std;

const int N = 60;
int n, m;
int g[N][N];

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;
    int dirs[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (g[i][j] == 1) {
                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) {
                        res += 1;
                        continue;
                    }
                    if (g[ni][nj] == 0) res += 1;
                }
            }
        }
    }
    cout << res << endl;

    return 0;
}

python3代码如下，

import sys 

if __name__ == "__main__":
    s = input()
    n, m = map(int, s.split())
    g = [[0] * m for _ in range(n)]
    for i in range(n):
        s = input()
        s = s.split()
        for j in range(m):
            x = int(s[j])
            g[i][j] = x 
    
    res = 0
    dirs = [[-1,0],[1,0],[0,-1],[0,1]]
    for i in range(n):
        for j in range(m):
            if g[i][j] == 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:
                        res += 1 
                        continue 
                    if g[ni][nj] == 0:
                        res += 1 
    print(res)

题目11：107. 寻找存在的路径

解题思路：并查集、bfs或dfs均可以求解此题。

C++代码如下，

//并查集解法
#include 

using namespace std;

const int N = 110;
int n, m;
int p[N];

int find(int x) {
    if (p[x] == x) return x;
    p[x] = find(p[x]);
    return p[x];
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) p[i] = i;
    
    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        int pa = find(a);
        int pb = find(b);
        p[pb] = pa;
    }
    
    int snode, enode;
    cin >> snode >> enode;
    if (find(snode) == find(enode)) {
        cout << "1" << endl;
    } else {
        cout << 0 << endl;
    }
    
    return 0;
}

//bfs解法
#include 

using namespace std;

const int N = 110;
int n, m;
bool st[N];

int main() {
    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);
        g[b].emplace_back(a);
    }

    int snode, enode;
    cin >> snode >> enode;

    memset(st, 0, sizeof st);
    queue<int> q;
    q.push(snode);
    st[snode] = true;
    while (!q.empty()) {
        int a = q.front();
        q.pop();
        for (int b : g[a]) {
            if (st[b] == false) {
                st[b] = true;
                q.push(b);
            }
        }
    }

    if (st[enode]) cout << 1 << endl;
    else cout << 0 << endl;

    return 0;
}

//dfs解法
#include 

using namespace std;

const int N = 110;
int n, m;
bool st[N];
unordered_map<int, vector<int>> g;

void dfs(int a) {
    st[a] = true;
    for (auto b : g[a]) {
        if (st[b] == false) {
            dfs(b);
        }
    }
    return;
}

int main() {
    cin >> n >> m;

    g.clear();
    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        g[a].emplace_back(b);
        g[b].emplace_back(a);
    }

    int snode, enode;
    cin >> snode >> enode;

    dfs(snode);

    if (st[enode]) cout << 1 << endl;
    else cout << 0 << endl;

    return 0;
}

python3代码如下，

#并查集解法
import os 
import sys 

if __name__ == "__main__":
    s = input()
    n, m = map(int, s.split())

    p = [i for i in range(n+1)]

    def find(x: int) -> int:
        global p 
        if p[x] == x:
            return x 
        p[x] = find(p[x])
        return p[x]

    for i in range(m):
        s = input()
        a, b = map(int, s.split())
        pa = find(a) 
        pb = find(b) 
        p[pa] = pb 
    
    s = input()
    snode, enode = map(int, s.split())

    if find(snode) == find(enode):
        print(1)
    else:
        print(0)

#bfs解法
import os 
import sys 
import collections 

if __name__ == "__main__":
    s = input()
    n, m = map(int, s.split())
    st = [False] * (n+1)

    g = collections.defaultdict(list)    
    for i in range(m):
        s = input()
        a, b = map(int, s.split())
        g[a].append(b)
        g[b].append(a)
    
    s = input()
    snode, enode = map(int, s.split())
    
    q = collections.deque([snode])
    st[snode] = True 
    while len(q) > 0:
        a = q.popleft()
        for b in g[a]:
            if st[b] == False:
                st[b] = True 
                q.append(b) 
    if st[enode] == True:
        print(1)
    else:
        print(0)

#dfs解法
import os 
import sys 
import collections 

def dfs(a: int) -> None:
    global st 
    st[a] = True 
    for b in g[a]:
        if st[b] == False:
            st[b] = True 
            dfs(b)
    return 

if __name__ == "__main__":
    s = input()
    n, m = map(int, s.split())
    st = [False] * (n+1)

    g = collections.defaultdict(list)    
    for i in range(m):
        s = input()
        a, b = map(int, s.split())
        g[a].append(b)
        g[b].append(a)

    s = input()
    snode, enode = map(int, s.split())

    dfs(snode)

    if st[enode] == True:
        print(1)
    else:
        print(0)

题目12：108. 冗余连接

解题思路：并查集，已经连通了，那就可以删除这条边。

C++代码如下，

#include 

using namespace std;

const int N = 1010;
int n;
int p[N];

int find(int x) {
    if (p[x] == x) return x;
    p[x] = find(p[x]);
    return p[x];
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) p[i] = i;

    for (int i = 0; i < n; ++i) {
        int a, b;
        cin >> a >> b;
        int pa = find(a);
        int pb = find(b);
        if (pa == pb) {
            cout << a << " " << b;
            break;
        } else {
            p[pa] = pb;
        }
    }

    return 0;
}

python3代码如下，

import os 
import sys 

def find(x: int) -> int:
    global p 
    if p[x] == x:
        return x 
    p[x] = find(p[x])
    return p[x]

if __name__ == "__main__":
    s = input()
    n = int(s)

    p = [i for i in range(n+1)]

    for i in range(n):
        s = input()
        a, b = map(int, s.split())
        pa = find(a)
        pb = find(b) 
        if pa == pb:
            print(f"{a} {b}")
            break 
        else:
            p[pa] = pb 

题目13：109. 冗余连接II

解题思路：如果存在入度为2的结点，选择较后出现的边，把它删除，删除之后需要保持树的形式。如果不存在入度为2的结点，则是一个环，删除较后出现的连通边即可。

C++代码如下，

#include 

using namespace std;

const int N = 1010;
int n;
int p[N];
vector<pair<int,int>> edges;
vector<int> ind;

int find(int x) {
    if (p[x] == x) return p[x];
    p[x] = find(p[x]);
    return p[x];
}

bool isTreeAfterRemove(pair<int,int> targetedge) {
    for (int i = 1; i <= n; ++i) p[i] = i;
    for (auto edge : edges) {
        if (edge == targetedge) continue;
        int a = edge.first, b = edge.second;
        int pa = find(a), pb = find(b);
        if (pa == pb) return false;
        else p[pa] = pb;
    }
    return true;
}

void getEdgeFromLoop() {
    for (int i = 1; i <= n; ++i) p[i] = i;
    for (auto edge : edges) {
        int a = edge.first, b = edge.second;
        int pa = find(a), pb = find(b);
        if (pa == pb) {
            cout << a << " " << b << endl;
        } else {
            p[pa] = pb;
        }
    }
    return;
}

int main() {
    cin >> n;
    edges.clear();
    ind = vector<int>(n+1,0);
    for (int i = 0; i < n; ++i) {
        int a, b;
        cin >> a >> b;
        edges.emplace_back(make_pair(a,b));
        ind[b]++;
    }
    
    int targetnode = -1; //度为2的结点
    for (int i = 1; i <= n; ++i) {
        if (ind[i] == 2) {
            targetnode = i;
            break;
        }
    }
    
    if (targetnode != -1) {
        vector<pair<int,int>> candidates;
        for (int i = n-1; i >= 0; --i) {
            if (edges[i].second == targetnode) {
                candidates.emplace_back(edges[i]);
            }
        }
        
        if (isTreeAfterRemove(candidates[0])) {
            cout << candidates[0].first << " " << candidates[0].second << endl;
            return 0;
        } else {
            cout << candidates[1].first << " " << candidates[1].second << endl;
            return 0;            
        }
    }
    
    getEdgeFromLoop();
    
    return 0;
}

python3代码如下，

import os 
import sys 
import copy 

def find(x: int) -> int:
    global p 
    if p[x] == x:
        return p[x]
    p[x] = find(p[x])
    return p[x]

def isTreeAfterRemove(targetedge: list) -> bool:
    global n, p, edges
    p = [i for i in range(n+1)]
    for edge in edges:
        if edge == targetedge:
            continue 
        a, b = edge[0], edge[1]
        pa, pb = find(a), find(b)
        if pa == pb:
            return False 
        else:
            p[pa] = pb 
    return True

def getEdgeFromLoop() -> None:
    global n, p, edges 
    p = [i for i in range(n+1)]
    for edge in edges:
        a, b = edge[0], edge[1]
        pa, pb = find(a), find(b)
        if pa == pb:
            print(f"{a} {b}")
            return 
        else:
            p[pa] = pb 
    return

if __name__ == "__main__":
    s = input()
    n = int(s)
    p = []
    edges = []
    ind = [0] * (n+1)
    for i in range(n):
        s = input()
        a, b = map(int, s.split())
        edges.append([a,b])
        ind[b] += 1 
    targetnode = -1 #入度为2的结点
    for i in range(1,n+1):
        if ind[i] == 2:
            targetnode = i 
            break 

    #如果存在入度为2的结点
    if targetnode != -1:
        targetedges = []
        for i in range(len(edges)-1,-1,-1):
            edge = edges[i]
            if edge[1] == targetnode:
                targetedges.append(edge)
        if isTreeAfterRemove(targetedges[0]):
            print(f"{targetedges[0][0]} {targetedges[0][1]}")
        else:
            print(f"{targetedges[1][0]} {targetedges[1][1]}")
    else:
        getEdgeFromLoop()

题目14：53. 寻宝（第七期模拟笔试）

解题思路：使用prim算法求解。详情参见acwing算法基础之搜索与图论–prim算法

C++代码如下，

#include 

using namespace std;

const int N = 10010;
int n, m;
int mindist[N];
bool st[N];
unordered_map<int, vector<pair<int,int>>> g;

void prim() {
    memset(mindist, 0x3f, sizeof mindist);
    memset(st, 0, sizeof st);
    
    //随机选择一个结点
    mindist[1] = 0;
    
    for (int k = 0; k < n; ++k) {
        int a = -1;
        int minv = 0x3f3f3f3f;
        for (int i = 1; i <= n; ++i) {
            if (st[i] == false && minv > mindist[i]) {
                a = i;
                minv = mindist[i];
            }
        }
        
        st[a] = true;
        for (auto iter : g[a]) {
            int b = iter.first;
            int w = iter.second;
            if (st[b] == false && mindist[b] > w) {
                mindist[b] = w;
            }
        }
    }
    
    int res = 0;
    for (int i = 1; i <= n; ++i) res += mindist[i];
    cout << res << endl;
    return;
}

int main() {
    cin >> n >> m;
    g.clear();
    for (int i = 0; i < m; ++i) {
        int a, b, w;
        cin >> a >> b >> w;
        g[a].emplace_back(make_pair(b,w));
        g[b].emplace_back(make_pair(a,w));
    }
    
    prim();
    
    return 0;
}

python3代码如下，

import collections 

def prim() -> None:
    global n, m, g 
    st = [False] * (n+1)
    mindist = [int(1e20)] * (n+1)
    mindist[1] = 0
    
    for k in range(n):
        #选择n个结点
        a = -1
        minv = int(1e20)
        for i in range(1,n+1):
            if st[i] == False and minv > mindist[i]:
                a = i 
                minv = mindist[i]
        
        st[a] = True 
        for b,w in g[a]:
            if st[b] == False and mindist[b] > w:
                mindist[b] = w 
    
    res = 0 
    for i in range(1,n+1):
        res += mindist[i] 
    print(res)
    return

if __name__ == "__main__":
    s = input()
    n, m = map(int, s.split())
    g = collections.defaultdict(list)
    for i in range(m):
        s = input()
        a, b, w = map(int, s.split())
        g[a].append([b,w])
        g[b].append([a,w])
    prim()

题目15：53. 寻宝（第七期模拟笔试）

解题思路：使用kruskal算法求解。详情参见acwing算法基础之搜索与图论–kruskal算法

C++代码如下，

#include 

using namespace std;

const int N = 1e5 + 10;
int n, m;
int p[N];
struct Edge {
    int a;
    int b;
    int w;
}edges[N];

int find(int x) {
    if (p[x] == x) return x;
    p[x] = find(p[x]);
    return p[x];
}

void kruskal() {
    sort(edges, edges+m, [](const Edge &a, const Edge &b) {
        return a.w < b.w;
    });
    
    for (int i = 1; i <= n; ++i) p[i] = i;
    
    long long res = 0;
    for (int i = 0; i < m; ++i) {
        int a = edges[i].a;
        int b = edges[i].b;
        int w = edges[i].w;
        int pa = find(a);
        int pb = find(b);
        if (pa != pb) {
            p[pa] = pb;
            res += w;
        }
    }
    
    cout << res << endl;
    return;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int a, b, w;
        cin >> edges[i].a >> edges[i].b >> edges[i].w;
    }
    
    kruskal();
    
    return 0;
}

python3代码如下，

import collections 

class Edge:
    def __init__(self, a: int, b: int, w: int) -> None:
        self.a = a 
        self.b = b 
        self.w = w 
        
def find(x: int) -> int:
    global p 
    if p[x] == x:
        return x 
    p[x] = find(p[x])
    return p[x]
        
def kruskal() -> None:
    global n, m, edges, p
    p = [i for i in range(n+1)]
    edges.sort(key = lambda x : x.w)
    
    res = 0
    for edge in edges:
        a = edge.a 
        b = edge.b 
        w = edge.w 
        pa = find(a)
        pb = find(b)
        if pa != pb:
            p[pa] = pb 
            res += w 
    print(res)
    return
        
if __name__ == "__main__":
    s = input()
    n, m = map(int, s.split())
    
    edges = []
    for i in range(m):
        s = input()
        a, b, w = map(int, s.split())
        edge = Edge(a,b,w)
        edges.append(edge)
    kruskal()

题目16：117. 软件构建

解题思路：拓扑排序，具体讲解可参见acwing算法提高之图论–拓扑排序

C++代码如下，

#include 

using namespace std;

const int N = 1e5 + 10;
int n, m;
int din[N];
unordered_map<int, vector<int>> g;

int main() {
    cin >> n >> m;
    g.clear();
    memset(din, 0, sizeof din);
    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        g[a].emplace_back(b);
        din[b] += 1;
    }
    
    queue<int> q;
    for (int i = 0; i < n; ++i) {
        if (din[i] == 0) q.push(i);
    }
    
    vector<int> res;
    while (!q.empty()) {
        int a = q.front();
        q.pop();
        res.emplace_back(a);
        for (auto b : g[a]) {
            din[b] -= 1;
            if (din[b] == 0) {
                q.push(b);
            }
        }
    }
    
    if (res.size() == n) {
        for (int i = 0; i+1 < res.size(); ++i) {
            cout << res[i] << " ";
        }
        cout << res.back() << endl;
    } else {
        cout << -1 << endl;
    }
    
    return 0;
}

python3代码如下，

import collections 

if __name__ == "__main__":
    s = input()
    n, m = map(int, s.split())
    din = [0] * (n+1)
    g = collections.defaultdict(list)
    for k in range(m):
        s = input()
        a, b = map(int, s.split())
        g[a].append(b)
        din[b] += 1 
    
    q = collections.deque([])
    for i in range(n):
        if din[i] == 0:
            q.append(i)
    res = []
    while len(q) > 0:
        a = q.popleft()
        res.append(a)
        for b in g[a]:
            din[b] -= 1 
            if din[b] == 0:
                q.append(b)
    #print(f"res={res}.")
    if len(res) == n:
        res = [str(x) for x in res]
        s = " ".join(res)
        print(s)
    else:
        print(-1)

题目17：47. 参加科学大会（第六期模拟笔试）

解题思路：dijkstra()算法。具体讲解参见acwing算法基础之搜索与图论–朴素版dijkstra算法

C++代码如下，

#include 

using namespace std;

const int N = 510;
int n, m;
unordered_map<int, vector<pair<int,int>>> g;
int mindist[N];
bool st[N];

void dijkstra() {
    memset(mindist, 0x3f, sizeof mindist);
    memset(st, 0, sizeof st);
    
    mindist[1] = 0;
    for (int k = 0; k < n-1; ++k) {
        int a = -1;
        int minv = 0x3f3f3f3f;
        for (int i = 1; i <= n; ++i) {
            if (st[i] == false && minv > mindist[i]) {
                a = i;
                minv = mindist[i];
            }
        }
        
        st[a] = true;
        for (auto [b, w] : g[a]) {
            if (st[b] == false && mindist[b] > mindist[a] + w) {
                mindist[b] = mindist[a] + w;
            }
        }
    }
    
    if (mindist[n] == 0x3f3f3f3f) {
        cout << -1 << endl;
    } else {
        cout << mindist[n] << endl;
    }
    return;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int a, b, w;
        cin >> a >> b >> w;
        g[a].emplace_back(make_pair(b,w));
    }
    
    dijkstra();
    
    return 0;
}

python3代码如下，

import collections 

def dijkstra() -> None:
    global n, m, g 
    st = [False] * (n+1)
    mindist = [int(1e20)] * (n+1)
    
    mindist[1] = 0 
    for k in range(n-1):
        a = -1 
        minv = int(1e20)
        for i in range(1,n+1):
            if st[i] == False and minv > mindist[i]:
                a = i 
                minv = mindist[i]
        
        st[a] = True 
        for b,w in g[a]:
            if st[b] == False and mindist[b] > mindist[a] + w:
                mindist[b] = mindist[a] + w 
    
    if mindist[n] == int(1e20):
        print(-1)
    else:
        print(mindist[n])
    return

if __name__ == "__main__":
    s = input()
    n, m = map(int, s.split())
    g = collections.defaultdict(list)
    for j in range(m):
        s = input()
        a, b, w = map(int, s.split())
        g[a].append([b,w])
    
    dijkstra()

题目18：47. 参加科学大会（第六期模拟笔试）

解题思路：堆优化版dijkstra算法。具体讲解参见acwing算法基础之搜索与图论–堆优化版dijkstra算法

C++代码如下，

#include 

using namespace std;

typedef pair<int,int> PII;

const int N = 510;
int n, m;
unordered_map<int, vector<pair<int,int>>> g;
int mindist[N];
bool st[N];

void dijkstra_opti() {
    memset(mindist, 0x3f, sizeof mindist);
    memset(st, 0, sizeof st);
    
    mindist[1] = 0;
    priority_queue<PII,vector<PII>,greater<PII>> hp; //小根堆
    hp.push(make_pair(0,1)); //first = mindist, second = node 
    
    while (!hp.empty()) {
        auto t = hp.top();
        hp.pop();
        int a = t.second;
        int amindist = t.first;
        
        for (auto [b,w] : g[a]) {
            if (st[b] == false && mindist[b] > amindist + w) {
                mindist[b] = amindist + w;
                hp.push(make_pair(mindist[b],b));
            }
        }
    }
    
    if (mindist[n] == 0x3f3f3f3f) {
        cout << -1 << endl;
    } else {
        cout << mindist[n] << endl;
    }
    return;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int a, b, w;
        cin >> a >> b >> w;
        g[a].emplace_back(make_pair(b,w));
    }
    
    dijkstra_opti();
    
    return 0;
}

python3代码如下，

import collections 
import heapq

def dijkstra_opti() -> None:
    global n, m, g 
    st = [False] * (n+1)
    mindist = [int(1e20)] * (n+1)
    
    mindist[1] = 0 
    hp = []
    heapq.heappush(hp, (0,1))
    
    while len(hp) > 0:
        amindist,a = heapq.heappop(hp)
        st[a] = True 
        for b,w in g[a]:
            if st[b] == False and mindist[b] > amindist + w:
                mindist[b] = amindist + w 
                heapq.heappush(hp, (mindist[b],b))
    
    if mindist[n] == int(1e20):
        print(-1)
    else:
        print(mindist[n])
    return

if __name__ == "__main__":
    s = input()
    n, m = map(int, s.split())
    g = collections.defaultdict(list)
    for j in range(m):
        s = input()
        a, b, w = map(int, s.split())
        g[a].append([b,w])
    
    dijkstra_opti()

题目19：94. 城市间货物运输 I

解题思路：存在负权边，使用bellman_ford算法。详细讲解参见acwing算法基础之搜索与图论–bellman-ford算法

C++代码如下，

#include 

using namespace std;

const int N = 1010, M = 1e4 + 10;
int n, m;
int mindist[N];
struct Edge {
    int a;
    int b;
    int w;
}edges[M];

void bellman_ford() {
    memset(mindist, 0x3f, sizeof mindist);
    mindist[1] = 0;
    
    for (int k = 0; k < n-1; ++k) {
        for (int j = 0; j < m; ++j) {
            int a = edges[j].a;
            int b = edges[j].b;
            int w = edges[j].w;
            if (mindist[a] != 0x3f3f3f3f && mindist[b] > mindist[a] + w) {
                mindist[b] = mindist[a] + w;
            }
        }
    }
    
    if (mindist[n] == 0x3f3f3f3f) {
        cout << "unconnected" << endl;
    } else {
        cout << mindist[n] << endl;
    }
    
    return;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int a, b, w;
        cin >> edges[i].a >> edges[i].b >> edges[i].w;
    }
    
    bellman_ford();
    
    return 0;
}

python3代码如下，

import os 

def bellman_ford() -> None:
    global n, m, edges 
    
    mindist = [int(1e20)] * (n+1)
    mindist[1] = 0 
    
    for i in range(n-1):
        update = False
        for j in range(m):
            a, b, w = edges[j]
            if mindist[a] != int(1e20) and mindist[b] > mindist[a] + w:
                mindist[b] = mindist[a] + w
                update = True 
        if not update:
            break 
    
    if mindist[n] == int(1e20):
        print("unconnected")
    else:
        print(mindist[n])
    return

if __name__ == "__main__":
    s = input()
    n, m = map(int, s.split())
    edges = [[0,0,0] for _ in range(m)]
    for j in range(m):
        s = input()
        a, b, w = map(int, s.split())
        edges[j] = [a, b, w]
    bellman_ford()

题目20：96. 城市间货物运输 III

解题思路：bellman_ford算法，记得备份一下上一次的松弛mindist结果。

C++代码如下，

#include 

using namespace std;

const int N = 1010, M = 1e4 + 10;
int n, m;
int mindist[N];
int backup[N];
struct {
    int a;
    int b;
    int w;
}edges[M];
int snode, enode, k;

void bellman_ford() {
    memset(mindist, 0x3f, sizeof mindist);
    mindist[snode] = 0;
    for (int i = 0; i < k; ++i) {
        memcpy(backup, mindist, sizeof mindist);
        for (int j = 0; j < m; ++j) {
            int a = edges[j].a;
            int b = edges[j].b;
            int w = edges[j].w;
            if (backup[a] != 0x3f3f3f3f && mindist[b] > backup[a] + w) {
                mindist[b] = backup[a] + w;
            }
        }
    }
    
    if (mindist[enode] == 0x3f3f3f3f) {
        cout << "unreachable" << endl;
    } else {
        cout << mindist[enode] << endl;
    }
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int a, b, w;
        cin >> edges[i].a >> edges[i].b >> edges[i].w;
    }
    cin >> snode >> enode >> k;
    k += 1;
    
    bellman_ford();
    return 0;
}

python3代码如下，

import os 
import copy 

def bellman_ford() -> None:
    global n, m, k, edges, snode, enode 
    mindist = [int(1e20)] * (n+1)
    mindist[snode] = 0 
    for i in range(k):
        backup = copy.deepcopy(mindist)
        for j in range(m):
            a, b, w = edges[j]
            if backup[a] != int(1e20) and mindist[b] > backup[a] + w:
                mindist[b] = backup[a] + w 
    if mindist[enode] == int(1e20):
        print("unreachable")
    else:
        print(mindist[enode])
    return

if __name__ == "__main__":
    s = input()
    n, m = map(int, s.split())
    edges = []
    for i in range(m):
        s = input()
        a, b, w = map(int, s.split())
        edges.append([a, b, w])
    s = input()
    snode, enode, k = map(int, s.split())
    k += 1 
    bellman_ford()

题目21：97. 小明逛公园

解题思路：floyd算法。详细讲解参见acwing算法提高之图论–floyd算法及其扩展应用

C++代码如下，

#include 

using namespace std;

const int N = 1010;
int d[N][N];
int n, m;

void floyd() {
    for (int i = 1; i <= n; ++i) d[i][i] = 0;
    
    for (int k = 1; k <= n; ++k) {
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }    

    return;
}

int main() {
    cin >> n >> m;
    memset(d, 0x3f, sizeof d);
    for (int i = 0; i < m; ++i) {
        int a, b, w;
        cin >> a >> b >> w;
        d[a][b] = w;
        d[b][a] = w;
    }
    
    floyd();
    
    int k;
    cin >> k;
    for (int i = 0; i < k; ++i) {
        int a, b;
        cin >> a >> b;
        if (d[a][b] == 0x3f3f3f3f) {
            cout << -1 << endl;
        } else {
            cout << d[a][b] << endl;
        }
    }
    
    return 0;
}

python3代码如下，

import os 

def floyd() -> None:
    global d, n, m 
    for i in range(1,n+1):
        d[i][i] = 0 
    
    for k in range(1,n+1):
        for i in range(1,n+1):
            for j in range(1,n+1):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
    return

if __name__ == "__main__":
    s = input()
    n, m = map(int, s.split())
    d = [[int(1e20)] * (n+1) for _ in range(n+1)]
    for i in range(m):
        s = input()
        a, b, w = map(int, s.split())
        d[a][b] = w 
        d[b][a] = w 
    floyd()
    
    k = int(input())
    for i in range(k):
        s = input()
        a, b = map(int, s.split())
        if d[a][b] == int(1e20):
            print(-1)
        else:
            print(d[a][b])

题目22：126. 骑士的攻击

解题思路：astar算法。详细讲解参见A * 算法精讲 （A star算法）

C++代码如下，

#include 

using namespace std;

const int N = 1010;
int n;
int d[N][N];
pair<int,int> snode, enode;
int dirs[8][2] = {{-2,-1},{-2,1},{-1,-2},{-1,2},{1,-2},{1,2},{2,-1},{2,1}};

struct Node {
    int x;
    int y;
    int w1;
    int w2;
    int w;
    
    bool operator< (const Node &a) const { //对应小根堆,greater
        return w > a.w;
    }
};


int compute_distance(int x1, int y1, int x2, int y2) {
    return (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1);
}

void astar() {
    memset(d, 0x3f, sizeof d);
    d[snode.first][snode.second] = 0;
    
    priority_queue<Node> hp;
    Node a;
    a.x = snode.first;
    a.y = snode.second;
    a.w1 = 0;
    a.w2 = compute_distance(snode.first, snode.second, enode.first, enode.second);
    a.w = a.w1 + a.w2;
    hp.push(a);
    
    while (!hp.empty()) {
        Node a = hp.top();
        int i = a.x;
        int j = a.y;
        if (i == enode.first && j == enode.second) {
            //找到答案，提前结束
            break;
        }
        hp.pop();
        for (int k = 0; k < 8; ++k) {
            int ni = i + dirs[k][0];
            int nj = j + dirs[k][1];
            if (ni < 1 || ni > 1000 || nj < 1 || nj > 1000) continue;
            if (d[ni][nj] == 0x3f3f3f3f) {
                Node b;
                b.x = ni;
                b.y = nj;      
                b.w1 = a.w1 + 5;
                b.w2 = compute_distance(ni, nj, enode.first, enode.second);
                b.w = b.w1 + b.w2;
                d[ni][nj] = d[i][j] + 1;
                hp.push(b);
            }
        }
    }
    
    return;
}

int main() {
    cin >> n;
    for (int i = 0; i < n; ++i) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        snode = make_pair(x1, y1);
        enode = make_pair(x2, y2);
        astar();
        cout << d[x2][y2] << endl;
    }
    
    return 0;
}

python3代码如下，

import heapq

class Node:
    def __init__(self, x: int, y: int, w1: int, w2: int) -> None:
        self.x = x 
        self.y = y
        self.w1 = w1 
        self.w2 = w2 
        self.w = self.w1 + self.w2 
        
    def __lt__(self, a) -> bool:
        return self.w < a.w 

def compute_distance(x1: int, y1: int, x2: int, y2: int) -> int:
    return (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1)

def astar() -> int:
    global x1, y1, x2, y2, dirs 
    mindist = [[int(1e20)] * 1010 for _ in range(1010)]
    hp = []
    heapq.heappush(hp, Node(x1,y1,0,compute_distance(x1,y1,x2,y2)))
    mindist[x1][y1] = 0 
    
    while len(hp) > 0:
        a = heapq.heappop(hp)
        i = a.x 
        j = a.y  
        if i == x2 and j == y2: #找到答案，结束
            break
        for k in range(8):
            ni = i + dirs[k][0]
            nj = j + dirs[k][1]
            if ni < 1 or ni > 1000 or nj < 1 or nj > 1000:
                continue 
            if mindist[ni][nj] != int(1e20):
                continue 
            b = Node(0,0,0,0)
            b.x = ni 
            b.y = nj 
            b.w1 = a.w1 + 5 
            b.w2 = compute_distance(ni,nj,x2,y2)
            b.w = b.w1 + b.w2 
            mindist[ni][nj] = mindist[i][j] + 1 
            heapq.heappush(hp, b)
    return mindist[x2][y2]

if __name__ == "__main__":
    n = int(input())
    for i in range(n):
        s = input()
        dirs = [[-2,-1], [-2,1], [-1,-2], [-1,2], [1,-2], [1,2], [2,-1], [2,1]]
        x1, y1, x2, y2 = map(int, s.split())
        res = astar()
        print(res)

3 参考

代码随想录官网