刷题 - 图论

在 染色的时候统计面积即可

visited[next_x][next_y] = true;
++area;

两个步骤：

• 从地图周边出发，将 ‘O’ 都做上标记，visited = true
• 然后再遍历一遍地图，遇到 ‘O’ 且没做过标记的，那么都是地图中间的 ‘O’ ，全部改成 ‘X’ 就行

class Solution {
public:
    // 太平洋：i == 0 || j == 0
    // 大西洋：i == m-1 || j == n-1
    // 方式1：从每个节点出发，如果可以到达太平洋且大西洋，记录结果
    // 方式2：从四周出发，逆向找可达节点

    int direction[4][2] = {-1, 0, 0, -1, 1, 0, 0, 1};
    // array<array<int, 2>, 4> direction = {-1, 0, 0, -1, 1, 0, 0, 1};
    void dfs(const vector<vector<int>>& heights, vector<vector<bool>>& visited, int x, int y) {
        for (int i = 0; i < 4; ++i) {
            int next_x = x + direction[i][0], next_y = y + direction[i][1];
            if (next_x < 0 || next_x >= heights.size() || \
                next_y < 0 || next_y >= heights[0].size() || \
                visited[next_x][next_y] == true ||
                heights[next_x][next_y] < heights[x][y]) {
                    continue;
            }
            visited[next_x][next_y] = true;
            dfs(heights, visited, next_x, next_y);
        }
    }

    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
        int m = heights.size(), n = heights[0].size();
        vector<vector<bool>> pacific_visited(m, vector<bool>(n, false));
        vector<vector<bool>> atlantic_visited(m, vector<bool>(n, false));
        
        for (int i = 0; i < n; ++i) {
            if (pacific_visited[0][i] == false) {
                pacific_visited[0][i] = true;
                dfs(heights, pacific_visited, 0, i);
            }
        }
        for (int i = 1; i < m; ++i) {
            if (pacific_visited[i][0] == false) {
                pacific_visited[i][0] = true;
                dfs(heights, pacific_visited, i, 0);
            }
        }

        for (int i = 0; i < n; ++i) {
            if (atlantic_visited[m-1][i] == false) {
                atlantic_visited[m-1][i] = true;
                dfs(heights, atlantic_visited, m-1, i);
            }
        }
        for (int i = 0; i < m - 1; ++i) {
            if (atlantic_visited[i][n-1] == false) {
                atlantic_visited[i][n-1] = true;
                dfs(heights, atlantic_visited, i, n-1);
            }
        }

        vector<vector<int>> result;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (pacific_visited[i][j] && atlantic_visited[i][j]) {
                    result.push_back({i,j});
                }
            }
        }

        return result;
    }
};

class Solution {
public:
    int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) {
        int m = maze.size(), n = maze[0].size();
        int x = entrance[0], y = entrance[1];
        queue<pair<int, int>> que;
        maze[x][y] = '+';
        que.push({x, y});
        // 定义四个方向：上、下、左、右
        const int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        int steps = 0;
        // 广度优先搜索
        while (!que.empty()) {
            int q_size = que.size();
            for (int i = 0; i < q_size; ++i) {
                auto [cur_x, cur_y] = que.front();
                que.pop();
                for (int d = 0; d < 4; ++d) {
                    int next_x = cur_x + dir[d][0];
                    int next_y = cur_y + dir[d][1];
                    // 检查边界条件
                    if (next_x < 0 || next_x >= m || \
                        next_y < 0 || next_y >= n || \
                        maze[next_x][next_y] == '+') {
                        continue;
                    }
                    // 如果到达边界并且不是入口，返回步数
                    if (next_x == 0 || next_x == m - 1 ||\
                         next_y == 0 || next_y == n - 1) {
                        return steps + 1;
                    }
                    // 标记为已访问，并将其加入队列
                    maze[next_x][next_y] = '+';
                    que.push({next_x, next_y});
                }
            }
            ++steps;
        }
        // 如果没有找到出口，返回 -1
        return -1;
    }
};

class Solution {
public:
    bool canConvert(const string& s1, const string& s2) {
        int diffCount = 0;
        for (int i = 0; i < s1.size(); ++i) {
            if (s1[i] != s2[i]) {
                if (++diffCount > 1) return false;
            }
        }
        return true;
    }

    int minMutation(string startGene, string endGene, vector<string>& bank) {
        if (startGene == endGene) return 0;
        int n = bank.size();
        int startIndex = -1, endIndex = -1;
        // 查找 startGene 和 endGene 在 bank 中的位置
        for (int i = 0; i < n; ++i) {
            if (bank[i] == endGene) endIndex = i;
            else if (bank[i] == startGene) startIndex = i;
        }
        // 如果终止基因不在 bank 中，直接返回 -1
        if (endIndex == -1) return -1;
        // 如果起始基因不在 bank 中，则将其作为附加节点处理
        if (startIndex == -1) startIndex = n;
        // 构建邻接表
        vector<list<int>> adj(n + 1);
        // 如果 startGene 不在 bank 中，构造与它相邻的节点
        if (startIndex == n) {
            for (int i = 0; i < n; ++i) {
                if (canConvert(startGene, bank[i])) {
                    adj[n].push_back(i);
                }
            }
        }
        // 构造 bank 中基因的邻接关系
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (canConvert(bank[i], bank[j])) {
                    adj[i].push_back(j);
                    adj[j].push_back(i);
                }
            }
        }
        // BFS 进行最短路径搜索
        queue<int> q;
        vector<bool> visited(n + 1, false);
        q.push(startIndex);
        visited[startIndex] = true;
        int steps = 0;
        while (!q.empty()) {
            int que_size = q.size();
            while (que_size--) {
                int node = q.front();
                q.pop();
                // 找到终止基因，返回步数
                if (node == endIndex) return steps;
                // 遍历邻居节点
                for (int neighbor : adj[node]) {
                    if (!visited[neighbor]) {
                        visited[neighbor] = true;
                        q.push(neighbor);
                    }
                }
            }
            ++steps; // 每一轮BFS增加一步
        }
        // 如果找不到转换路径，返回 -1
        return -1;
    }
};

和最小基因变化基本没区别

• 本题为有向无环图，如果存在环的话需要加一个 visited 数组
• 时间复杂度：O(2^n)，最坏情况下可能有 2 的 n 次方条路径，其中 n 是图的节点数。
• 空间复杂度：O(n)，递归深度最深为 n（即从 0 到目标节点的最长路径长度），以及存储路径所需的空间。

// 有向无环图求所有可行路径
// 如果存在环的话需要加一个 visited 数组
class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;
    void dfs(vector<vector<int>>& graph, int start) {
        if (start == graph.size() - 1) {
            result.push_back(path);
        }
        for (auto& next : graph[start]) {
            path.push_back(next);
            dfs(graph, next);
            path.pop_back();
        }
    }

    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
        path.push_back(0);
        dfs(graph, 0);
        return result; 
    }
};

如果边的两个节点已经出现在同一个集合里，说明这条边的两个节点已经连在一起了，再加入这条边一定就出现环了。

    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        int n = edges.size();
        UnionSet union_set(n + 1);
        for (auto& edge : edges) {
            int u = edge[0], v = edge[1];
            if (union_set.IsConnected(u, v)) {
                return {u, v};
            } else {
                union_set.Join(u, v);
            }
        }
        return {};
    }

参考链接：【困难题简单做】分类讨论+并查集，击破hard

class Solution {
public:
    // 查找冗余的有向边
    vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {
        int n = edges.size();
        vector<int> parent(n + 1, 0);
        vector<int> edge_to_remove1, edge_to_remove2;
        int two_in_node = -1;

        // 检测入度为2的情况
        for (auto& edge : edges) {
            int u = edge[0], v = edge[1];
            if (parent[v] == 0) {
                parent[v] = u;
            } else {
                // 发现入度为2的节点 v
                two_in_node = v;
                edge_to_remove1 = {parent[v], v}; // 之前的边
                edge_to_remove2 = {u, v}; // 当前的边
                break;
            }
        }

        // 重建并查集，处理有环的情况
        UnionSet union_set(n + 1);
        for (auto& edge : edges) {
            int u = edge[0], v = edge[1];
            if (edge == edge_to_remove2) {
                // 跳过第二条边，先验证第一条边
                continue;
            }
            if (union_set.IsConnected(u, v)) {
                // 出现环
                //  + 如果不存在入度为2的节点，只需要考虑环的问题
                //  + 说明正是[u,v]导致环的出现，删除 [u, v] 即可    
                if (two_in_node == -1) return edge;

                //  + 存在入度为 2 的节点
                //  + edge_to_remove1 必然属于这个环的一部分
                //  + 否则就会出现两条不合法的边了，不合题意
                //  + 因此我们删除两个不合法的交集，也即 edge_to_remove1
                return edge_to_remove1;
            }
            union_set.Join(u, v);
        }

        // 循环正常结束，说明没有出现环
        // 说明异常情况为：存在入度为 2 的节点
        // 删除最后一条导致入度为 2 的边，也即 edge_to_remove2
        return edge_to_remove2;
    }
};

• 遍历所有边，记录所有节点的入度，将入度为 0 的节点加入队列和结果数组
• 当队列不为空时，从队列中弹出节点，遍历节点的所有邻居，将邻居的入度减1，如果此时邻居的入度为0，则将该邻居加入队列和结果数组
• 队列为空，若结果数组的长度不等于节点个数，说明存在环，否则返回结果数组

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<int> indegrees(numCourses, 0);
        vector<list<int>> adj(numCourses);
        for (const auto& pre : prerequisites) {
            ++indegrees[pre[0]];
            adj[pre[1]].push_back(pre[0]);
        }
        int count = 0;
        queue<int> que;
        for (int i = 0; i < numCourses; ++i) {
            if (indegrees[i] == 0) {
                que.push(i);
                ++count;
            }
        }
        while (!que.empty()) {
            int cur = que.front();
            que.pop();
            for (auto next : adj[cur]) {
                if (--indegrees[next] == 0) {
                    que.push(next);
                    ++count;
                }
            }
        }
        return (count == numCourses);
    }
};

• 使用 堆来存储当前最短路径节点 {节点到起点的距离, 节点索引}
• 每次从优先队列中选择当前距离最小的未处理节点

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
#include <list>
using namespace std;

int dijkstra(vector<list<pair<int, int>>>& adj_list) {
    int n = adj_list.size() - 1; 
    int start = 1, end = n;
    vector<int> costs(n + 1, INT_MAX);	// 记录距离
    vector<int> visited(n + 1, false);	// 标记是否找到最短路		
    // 堆存储 {节点到起点的距离，节点索引}
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    // 初始化
    costs[start] = 0;
    pq.push({0, start});

    while (!pq.empty()) {
    	// 每次从优先队列中选择当前距离最小的未处理节点
        int cost = pq.top().first;
        int cur = pq.top().second;
        pq.pop();
        if (visited[cur]) continue;	// 节点已经访问过，跳过
        visited[cur] = true;			// 未访问过，标记为访问过
        if (cur == end) return costs[end];	// 到达终点
        // 遍历相邻节点
        for (auto& [next, time] : adj_list[cur]) {
            if (!visited[next] && costs[cur] + time < costs[next]) {
            	// 找到更短的路径了   
                costs[next] = costs[cur] + time;
                pq.push({costs[next], next});
            }
        }
    }
    return -1;  // 如果没有路径到达终点
}

int main(int argc, char* argv[]) {
    if (argc == 1) return -1;
    freopen(argv[1], "r", stdin);
    int n, m;
    cin >> n >> m;  // n 个 车站 m 条公路
    vector<list<pair<int, int>>> adj_list(n + 1);
    for (int i = 0; i < m; ++i) {   // 输入 m 条边：起点 终点 和 时间
        int start, end, time;
        cin >> start >> end >> time;
        adj_list[start].push_back({end, time});
    }

    cout << dijkstra(adj_list) << endl;
    return 0;
}

#include <iostream>
#include <vector>
#include <list>
#include <climits>
using namespace std;

int main() {
    int n, m, p1, p2, val;
    cin >> n >> m;

    vector<vector<vector<int>>> grid(n + 1, vector<vector<int>>(n + 1, vector<int>(n + 1, INT_MAX)));  // 因为边的最大距离是10^4
    for(int i = 0; i < m; i++){
        cin >> p1 >> p2 >> val;
        grid[p1][p2][0] = val;
        grid[p2][p1][0] = val; // 注意这里是双向图

    }
    // 开始 floyd
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (grid[i][k][k-1] == INT_MAX || grid[k][j][k-1] == INT_MAX) {
                    grid[i][j][k] = grid[i][j][k-1];
                } else {
                    grid[i][j][k] = min(grid[i][j][k-1], grid[i][k][k-1] + grid[k][j][k-1]);
                }      
            }
        }
    }
    // 输出结果
    int z, start, end;
    cin >> z;
    while (z--) {
        cin >> start >> end;
        if (grid[start][end][n] == INT_MAX) cout << -1 << endl;
        else cout << grid[start][end][n] << endl;
    }
}

空间优化

#include <iostream>
#include <vector>
#include <list>
#include <climits>
using namespace std;

int main() {
    int n, m, p1, p2, val;
    cin >> n >> m;

    vector<vector<int>> grid(n + 1, vector<int>(n + 1, INT_MAX));  // 因为边的最大距离是10^4
    for(int i = 0; i < m; i++){
        cin >> p1 >> p2 >> val;
        grid[p1][p2] = val;
        grid[p2][p1] = val; // 注意这里是双向图

    }
    // 开始 floyd
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (grid[i][k] != INT_MAX && grid[k][j] != INT_MAX) {
                    grid[i][j] = min(grid[i][j], grid[i][k] + grid[k][j]);
                }      
            }
        }
    }
    // 输出结果
    int z, start, end;
    cin >> z;
    while (z--) {
        cin >> start >> end;
        if (grid[start][end] == INT_MAX) cout << -1 << endl;
        else cout << grid[start][end] << endl;
    }
}

图-最小生成树-Prim(普里姆)算法和Kruskal(克鲁斯卡尔)算法

#include<iostream>
#include<vector>
#include <climits>

using namespace std;

int main() {
    int v, e;   // 顶点数和边数
    cin >> v >> e;
    
    vector<vector<int>> grid(v + 1, vector<int>(v + 1, INT_MAX));
    
    int x, y, k;    // 起点，终点和权值
    while (e--) {
        cin >> x >> y >> k;
        grid[x][y] = k;
        grid[y][x] = k;   // 无向图
    }
    
    // Prim算法部分
    vector<int> minDist(v + 1, INT_MAX);        // 所有节点到最小生成树的最小距离
    vector<bool> isInTree(v + 1, false);        // 是否已经在最小生成树中
    minDist[1] = 0;                             // 从第1个节点开始
    
    int result = 0;
    
    for (int i = 1; i <= v; i++) {
        int cur = -1;
        int minVal = INT_MAX;

        // 找到距离当前生成树最近的节点
        for (int j = 1; j <= v; j++) {
            if (!isInTree[j] && minDist[j] < minVal) {
                minVal = minDist[j];
                cur = j;
            }
        }

        // 如果没有找到合适的节点，则图不连通
        if (cur == -1) {
            cout << "Graph is not connected" << endl;
            return -1;
        }

        isInTree[cur] = true;
        result += minVal;  // 把该点与生成树相连的最小边的权值加入结果

        // 更新其他节点到生成树的最短距离
        for (int j = 1; j <= v; j++) {
            if (!isInTree[j] && grid[cur][j] != INT_MAX && grid[cur][j] < minDist[j]) {
                minDist[j] = grid[cur][j];
            }
        }
    }
    
    // 输出最小生成树的权重
    cout << result << endl;

    return 0;
}