代码随想录leetcode200题之图论

2024-06-29 1175阅读

目录

  • 1 介绍
  • 2 训练
  • 3 参考

    1 介绍

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

    代码随想录leetcode200题之图论
    （图片来源网络，侵删）

    2 训练

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

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

    C++代码如下，

    #include 
using namespace std;
int n, m;
unordered_map g;
vector 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  a >> b;
        g[a].emplace_back(b);
    }
    cur.emplace_back(1);
    dfs(-1, 1);
    if (has_path == false) cout  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 = n || 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 > g[i][j];
        }
    }
    
    memset(st, 0, sizeof st);
    int res = 0;
    for (int i = 0; i > n >> m;
    for (int i = 0; i > g[i][j];
        }
    }
    
    memset(st, 0, sizeof st);
    int res = 0;
    for (int i = 0; i = 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 = n 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 = n || 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 > n >> m;
    for (int i = 0; i > g[i][j];
        }
    }
    
    int res = 0;
    for (int i = 0; i > n >> m;
    for (int i = 0; i > g[i][j];
        }
    }
    memset(st, 0, sizeof st);
    int res = 0;
    for (int i = 0; i = 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 = n 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 = n || 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 > n >> m;
    for (int i = 0; i > g[i][j];
        }
    }
    
    memset(st, 0, sizeof st);
    
    for (int j = 0; j > n >> m;
    for (int i = 0; i > g[i][j];
        }
    }
    memset(st, 0, sizeof st);
    for (int i = 0; i = 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 = n 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 = n || 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 > n >> m;
    for (int i = 0; i > g[i][j];
        }
    }
    
    memset(st, 0, sizeof st);
    
    for (int j = 0; j  m;
    for (int i = 0; i > g[i][j];
        }
    }
    memset(st, 0, sizeof st);
    for (int i = 0; i = n 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 = n || 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 > g[i][j];
        }
    }
    memset(st1, 0, sizeof st1);
    memset(st2, 0, sizeof st2);
    for (int j = 0; j  n >> m;
    for (int i = 0; i > g[i][j];
        }
    }
    memset(st1, 0, sizeof st1);
    memset(st2, 0, sizeof st2);
    //边界1
    for (int i = 0; i  

    #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 = n 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 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 = n || 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 > n >> m;
    for (int i = 0; i > g[i][j];
        }
    }
    memset(st, 0, sizeof st);
    bool is_all_ones = true;
    int mark = 2;
    for (int i = 0; i > n >> m;
    for (int i = 0; i > g[i][j];
        }
    }
    memset(st, 0, sizeof st);
    bool is_all_ones = true;
    int mask = 2;
    for (int i = 0; i = 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 = n 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 = n 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 = n 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  n;
    cin >> snode >> enode;
    for (int i = 0; i > t;
        nodes.insert(t);
    }
    //把起点和终点也加入nodes变量中
    nodes.insert(snode);
    nodes.insert(enode);
    vector vec_nodes;
    for (auto x : nodes) {
        vec_nodes.emplace_back(x);
    }
    unordered_map g;
    for (int i = 0; i  n >> m;
    g.clear();
    for (int i = 0; i > a >> b;
        g[a].emplace_back(b); //单向边
    }
    st.clear();
    st = vector(n+1, false);
    dfs(1);
    for (int i = 1; i 
        if (st[i] == false) {
            cout 
    int n, m;
    cin  n  m;
    unordered_map
        int a, b;
        cin > a >> b;
        g[a].emplace_back(b); //单向边
    }
    vector st(n+1, false);
    queue 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 
        if (st[i] == false) {
            cout 
    cin  n > m;
    for (int i = 0; i > g[i][j];
        }
    }
    int res = 0;
    int dirs[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
    for (int i = 0; i = n || nj = m) {
                        res += 1;
                        continue;
                    }
                    if (g[ni][nj] == 0) res += 1;
                }
            }
        }
    }
    cout = 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 
        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 
        cout 
    cin  n  m;
    unordered_map g;
    for (int i = 0; i > a >> b;
        g[a].emplace_back(b);
        g[b].emplace_back(a);
    }
    int snode, enode;
    cin >> snode >> enode;
    memset(st, 0, sizeof st);
    queue 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 
    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 > a >> b;
        g[a].emplace_back(b);
        g[b].emplace_back(a);
    }
    int snode, enode;
    cin >> snode >> enode;
    dfs(snode);
    if (st[enode]) cout
VPS购买请点击我

免责声明：我们致力于保护作者版权，注重分享，被刊用文章因无法核实真实出处，未能及时与作者取得联系，或有版权异议的，请联系管理员，我们会立即处理! 部分文章是来自自研大数据AI进行生成,内容摘自(百度百科,百度知道,头条百科,中国民法典,刑法,牛津词典,新华词典,汉语词典,国家院校,科普平台)等数据,内容仅供学习参考,不准确地方联系删除处理! 图片声明：本站部分配图来自人工智能系统AI生成,觅知网授权图片,PxHere摄影无版权图库和百度，360，搜狗等多加搜索引擎自动关键词搜索配图，如有侵权的图片，请第一时间联系我们，邮箱：ciyunidc@ciyunshuju.com。本站只作为美观性配图使用,无任何非法侵犯第三方意图,一切解释权归图片著作权方,本站不承担任何责任。如有恶意碰瓷者,必当奉陪到底严惩不贷!

相关阅读

目录[+]