拓扑排序与图遍历#

拓扑排序用于有向无环图（DAG），它能给出一个所有节点满足其前驱节点都在其之前的线性序列。这在处理依赖关系（如课程安排、编译顺序）时非常有用。核心算法是 Kahn 算法（基于BFS和入度）和基于DFS的算法。

Example Problem Leetcode 207. 课程表 & 210. 课程表 II

原理： 这两个问题是拓扑排序的经典应用。要完成所有课程，课程依赖关系中不能存在环。

• 课程表 (207)：判断是否存在环。
• 课程表 II (210)：如果无环，返回一个可行的学习顺序。

Kahn 算法的思路是：

1. 构建图，并统计所有节点的入度（即有多少门先修课）。
2. 将所有入度为 0 的节点（没有先修课的课程）加入队列。
3. 当队列不为空时，出队一个节点，加入拓扑排序结果中。
4. 遍历该节点的所有邻居（依赖该课程的后续课程），将其入度减 1。如果邻居的入度变为 0，则入队。
5. 循环结束后，如果结果列表中的节点数等于总节点数，则拓扑排序成功；否则，图中存在环。

#include <vector>
#include <queue>

class Solution {
public:
    // Leetcode 210
    std::vector<int> findOrder(int numCourses, std::vector<std::vector<int>>& prerequisites) {
        std::vector<std::vector<int>> graph(numCourses);
        std::vector<int> in_degree(numCourses, 0);
        
        for (const auto& p : prerequisites) {
            graph[p[1]].push_back(p[0]);
            in_degree[p[0]]++;
        }
        
        std::queue<int> q;
        for (int i = 0; i < numCourses; ++i) {
            if (in_degree[i] == 0) {
                q.push(i);
            }
        }
        
        std::vector<int> result;
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            result.push_back(u);
            
            for (int v : graph[u]) {
                in_degree[v]--;
                if (in_degree[v] == 0) {
                    q.push(v);
                }
            }
        }
        
        if (result.size() == numCourses) {
            return result;
        }
        return {}; // Leetcode 207 would return false here
    }
};

Example Problem Leetcode 1462. 课程表 IV

原理： 判断课程 u 是否是课程 v 的先修课程，本质上是查询图中节点 u 是否可达节点 v。我们可以预先计算出图中所有节点对之间的可达性（传递闭包）。

1. Floyd-Warshall: 将图看作邻接矩阵 adj，adj[i][j] = true 如果 i 是 j 的直接先修。然后用 Floyd-Warshall 算法计算传递闭包：adj[i][j] = adj[i][j] || (adj[i][k] && adj[k][j])。
2. 多次BFS/DFS: 从每个节点 i 出发，通过图遍历（BFS或DFS）找出所有它能到达的节点 j，并记录下来。

class Solution {
public:
    std::vector<bool> checkIfPrerequisite(int numCourses, std::vector<std::vector<int>>& prerequisites, std::vector<std::vector<int>>& queries) {
        std::vector<std::vector<bool>> is_prereq(numCourses, std::vector<bool>(numCourses, false));
        
        for (const auto& p : prerequisites) {
            is_prereq[p[0]][p[1]] = true;
        }
        
        // Floyd-Warshall to find all-pairs reachability
        for (int k = 0; k < numCourses; ++k) {
            for (int i = 0; i < numCourses; ++i) {
                for (int j = 0; j < numCourses; ++j) {
                    is_prereq[i][j] = is_prereq[i][j] || (is_prereq[i][k] && is_prereq[k][j]);
                }
            }
        }
        
        std::vector<bool> result;
        for (const auto& q : queries) {
            result.push_back(is_prereq[q[0]][q[1]]);
        }
        return result;
    }
};

Example Problem Leetcode 1311. 获取你好友已观看的视频

原理： 这是一个在图上进行限定层数广度优先搜索（BFS）的问题。

1. 从你的 id 开始进行 BFS，层数 level 从 1 开始。
2. 当 level 达到给定的 level 时，收集该层所有好友观看过的视频。
3. 使用哈希表统计视频出现的频率，并按频率和视频名字典序排序。

#include <vector>
#include <string>
#include <queue>
#include <map>
#include <algorithm>

class Solution {
public:
    std::vector<std::string> watchedVideosByFriends(std::vector<std::vector<std::string>>& watchedVideos, std::vector<std::vector<int>>& friends, int id, int level) {
        int n = friends.size();
        std::queue<std::pair<int, int>> q;
        q.push({id, 0});
        std::vector<bool> visited(n, false);
        visited[id] = true;
        
        std::vector<int> level_friends;
        
        while (!q.empty()) {
            auto [curr_id, curr_level] = q.front();
            q.pop();
            
            if (curr_level == level) {
                level_friends.push_back(curr_id);
            }
            if (curr_level > level) break;
            
            for (int friend_id : friends[curr_id]) {
                if (!visited[friend_id]) {
                    visited[friend_id] = true;
                    q.push({friend_id, curr_level + 1});
                }
            }
        }
        
        std::map<std::string, int> freq;
        for (int friend_id : level_friends) {
            for (const std::string& video : watchedVideos[friend_id]) {
                freq[video]++;
            }
        }
        
        std::vector<std::pair<int, std::string>> sorted_videos;
        for (auto const& [video, count] : freq) {
            sorted_videos.push_back({count, video});
        }
        
        std::sort(sorted_videos.begin(), sorted_videos.end());
        
        std::vector<std::string> result;
        for (const auto& p : sorted_videos) {
            result.push_back(p.second);
        }
        
        return result;
    }
};

Example Problem Leetcode 2360. 图中的最长环

原理： 题目给的是一个功能图（每个节点出度为1）。在这种图中，从任何节点出发，最终要么到达一个环，要么路径结束。我们可以用DFS来遍历图，同时记录路径。

1. 使用 visited 数组标记已完全探索过的节点（确定不在任何未发现的环中）。
2. 对于每个未访问的节点，开始DFS。使用一个 path_visited 哈希表记录当前路径上的节点及其路径长度（或时间戳）。
3. 如果在DFS中遇到一个已经在 path_visited 中的节点，说明找到了一个环。环的长度为 当前路径长度 - 首次访问该节点时的路径长度。
4. DFS结束后，将当前路径上的所有节点标记到 visited 中，避免重复计算。

#include <vector>
#include <algorithm>

class Solution {
public:
    int longestCycle(std::vector<int>& edges) {
        int n = edges.size();
        std::vector<bool> visited(n, false);
        int max_cycle = -1;

        for (int i = 0; i < n; ++i) {
            if (visited[i]) continue;
            
            std::vector<int> path_visited(n, 0);
            int dist = 0;
            int curr = i;
            
            while (curr != -1 && !visited[curr]) {
                if (path_visited[curr] > 0) { // Found a cycle
                    max_cycle = std::max(max_cycle, dist - path_visited[curr] + 1);
                    break;
                }
                path_visited[curr] = dist + 1;
                dist++;
                visited[curr] = true; // Mark as visited for this path traversal
                curr = edges[curr];
            }
        }
        return max_cycle;
    }
};

图与动态规划/博弈论#

许多图问题，特别是在网格或DAG上，可以利用动态规划（通常是记忆化搜索）来求解。当问题涉及两个对立玩家时，就进入了图博弈论的范畴。

Example Problem Leetcode 1728. 猫和老鼠 II

原理： 这是一个在网格图上的博弈论问题。我们需要确定在最优策略下，老鼠是否能赢。

1. 状态定义：游戏的状态由 (mouse_row, mouse_col, cat_row, cat_col, turn) 决定，其中 turn 表示轮到谁（0为老鼠，1为猫）。
2. 结果定义：每个状态有三种可能的结果：老鼠赢 (MOUSE_WIN), 猫赢 (CAT_WIN), 或平局/未知 (DRAW)。
3. 逆向推理 (BFS)：我们从已知的终局状态开始，反向推导所有其他状态的结果。
   • 终局状态：老鼠在食物处（老鼠赢），猫鼠同格（猫赢），猫在食物处（猫赢）。
   • 状态转移：
     • 如果一个状态是老鼠的回合，并且老鼠可以移动到一个老鼠赢的状态，那么当前状态也是老鼠赢。
     • 如果一个状态是猫的回合，并且猫可以移动到一个猫赢的状态，那么当前状态也是猫赢。
     • 如果一个状态是老鼠的回合，并且它所有的下一步都通向猫赢的状态，那么当前状态是猫赢。
     • 如果一个状态是猫的回合，并且它所有的下一步都通向老鼠赢的状态，那么当前状态是老鼠赢。
4. 拓扑排序思想：我们可以用一个 degrees 数组记录每个状态有多少个“未确定结果”的后续走法。当一个状态的所有后续走法都确定为对手赢时，该状态就确定为输。我们将结果确定的状态加入队列，并更新其前驱状态的 degrees，这类似于拓扑排序。

#include <vector>
#include <string>
#include <queue>

class Solution {
public:
    bool canMouseWin(std::vector<std::string>& grid, int catJump, int mouseJump) {
        int rows = grid.size(), cols = grid[0].size();
        int food_r, food_c, mouse_r, mouse_c, cat_r, cat_c;
        for (int r = 0; r < rows; ++r) {
            for (int c = 0; c < cols; ++c) {
                if (grid[r][c] == 'F') { food_r = r; food_c = c; }
                else if (grid[r][c] == 'M') { mouse_r = r; mouse_c = c; }
                else if (grid[r][c] == 'C') { cat_r = r; cat_c = c; }
            }
        }

        // state: [mouse_pos, cat_pos, turn], pos = r * cols + c
        // result: 0: DRAW, 1: MOUSE_WIN, 2: CAT_WIN
        int states[rows][cols][rows][cols][2];
        int degrees[rows][cols][rows][cols][2];
        std::memset(states, 0, sizeof(states));
        std::memset(degrees, 0, sizeof(degrees));

        int dr[] = {-1, 1, 0, 0}, dc[] = {0, 0, -1, 1};

        for (int mr = 0; mr < rows; ++mr) {
            for (int mc = 0; mc < cols; ++mc) {
                if (grid[mr][mc] == '#') continue;
                for (int cr = 0; cr < rows; ++cr) {
                    for (int cc = 0; cc < cols; ++cc) {
                        if (grid[cr][cc] == '#') continue;
                        // Mouse's turn
                        for (int i = 0; i < 4; ++i) {
                            for (int jump = 0; jump <= mouseJump; ++jump) {
                                int nmr = mr + dr[i] * jump, nmc = mc + dc[i] * jump;
                                if (nmr < 0 || nmr >= rows || nmc < 0 || nmc >= cols || grid[nmr][nmc] == '#') break;
                                degrees[mr][mc][cr][cc][0]++;
                            }
                        }
                        // Cat's turn
                        for (int i = 0; i < 4; ++i) {
                            for (int jump = 0; jump <= catJump; ++jump) {
                                int ncr = cr + dr[i] * jump, ncc = cc + dc[i] * jump;
                                if (ncr < 0 || ncr >= rows || ncc < 0 || ncc >= cols || grid[ncr][ncc] == '#') break;
                                degrees[mr][mc][cr][cc][1]++;
                            }
                        }
                    }
                }
            }
        }

        std::queue<std::tuple<int, int, int, int, int>> q;

        for (int r = 0; r < rows; ++r) {
            for (int c = 0; c < cols; ++c) {
                if (grid[r][c] == '#') continue;
                // Terminal states
                if (r == food_r && c == food_c) continue;
                for (int turn = 0; turn < 2; ++turn) {
                    // Cat wins by catching mouse
                    states[r][c][r][c][turn] = 2;
                    q.emplace(r, c, r, c, turn);
                    // Mouse wins by reaching food
                    states[food_r][food_c][r][c][turn] = 1;
                    q.emplace(food_r, food_c, r, c, turn);
                }
            }
        }

        while (!q.empty()) {
            auto [mr, mc, cr, cc, turn] = q.front();
            q.pop();
            int result = states[mr][mc][cr][cc][turn];
            int prev_turn = 1 - turn;

            if (prev_turn == 0) { // Previous turn was mouse's
                for (int i = 0; i < 4; ++i) {
                    for (int jump = 0; jump <= mouseJump; ++jump) {
                        int pmr = mr - dr[i] * jump, pmc = mc - dc[i] * jump;
                        if (pmr < 0 || pmr >= rows || pmc < 0 || pmc >= cols || grid[pmr][pmc] == '#') break;
                        if (states[pmr][pmc][cr][cc][prev_turn] == 0) {
                            if (result == 1) { // Mouse found a winning move
                                states[pmr][pmc][cr][cc][prev_turn] = 1;
                                q.emplace(pmr, pmc, cr, cc, prev_turn);
                            } else { // One path to cat-win is removed
                                degrees[pmr][pmc][cr][cc][prev_turn]--;
                                if (degrees[pmr][pmc][cr][cc][prev_turn] == 0) {
                                    states[pmr][pmc][cr][cc][prev_turn] = 2;
                                    q.emplace(pmr, pmc, cr, cc, prev_turn);
                                }
                            }
                        }
                    }
                }
            } else { // Previous turn was cat's
                 for (int i = 0; i < 4; ++i) {
                    for (int jump = 0; jump <= catJump; ++jump) {
                        int pcr = cr - dr[i] * jump, pcc = cc - dc[i] * jump;
                        if (pcr < 0 || pcr >= rows || pcc < 0 || pcc >= cols || grid[pcr][pcc] == '#') break;
                        if (states[mr][mc][pcr][pcc][prev_turn] == 0) {
                            if (result == 2) { // Cat found a winning move
                                states[mr][mc][pcr][pcc][prev_turn] = 2;
                                q.emplace(mr, mc, pcr, pcc, prev_turn);
                            } else {
                                degrees[mr][mc][pcr][pcc][prev_turn]--;
                                if (degrees[mr][mc][pcr][pcc][prev_turn] == 0) {
                                    states[mr][mc][pcr][pcc][prev_turn] = 1;
                                    q.emplace(mr, mc, pcr, pcc, prev_turn);
                                }
                            }
                        }
                    }
                }
            }
        }
        return states[mouse_r][mouse_c][cat_r][cat_c][0] == 1;
    }
};

Example Problem Leetcode 329. 矩阵中的最长递增路径

原理： 将矩阵看作一个图，每个单元格是一个节点，如果两个相邻单元格的值满足递增关系，则存在一条有向边。问题是求图中的最长路径。这是一个DAG（因为路径必须递增，所以无环），可以用DFS + 记忆化来解决。

1. 定义 dp[r][c] 为从单元格 (r, c) 出发的最长递增路径的长度。
2. 对每个单元格 (r, c) 调用DFS函数。
3. DFS函数中，如果 dp[r][c] 已计算过，直接返回。否则，探索四个方向的邻居 (nr, nc)，如果 matrix[nr][nc] > matrix[r][c]，则 dp[r][c] 可以更新为 1 + dfs(nr, nc)。
4. 取所有方向的最大值更新 dp[r][c]，并用一个全局变量记录所有 dp 值中的最大值。

#include <vector>
#include <algorithm>

class Solution {
public:
    int longestIncreasingPath(std::vector<std::vector<int>>& matrix) {
        if (matrix.empty()) return 0;
        int rows = matrix.size(), cols = matrix[0].size();
        std::vector<std::vector<int>> dp(rows, std::vector<int>(cols, 0));
        int max_len = 0;
        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < cols; ++j) {
                max_len = std::max(max_len, dfs(matrix, i, j, dp));
            }
        }
        return max_len;
    }

private:
    int dfs(const std::vector<std::vector<int>>& matrix, int r, int c, std::vector<std::vector<int>>& dp) {
        if (dp[r][c] != 0) return dp[r][c];
        
        int max_path = 1;
        int rows = matrix.size(), cols = matrix[0].size();
        int dr[] = {-1, 1, 0, 0};
        int dc[] = {0, 0, -1, 1};
        
        for (int i = 0; i < 4; ++i) {
            int nr = r + dr[i];
            int nc = c + dc[i];
            if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && matrix[nr][nc] > matrix[r][c]) {
                max_path = std::max(max_path, 1 + dfs(matrix, nr, nc, dp));
            }
        }
        
        return dp[r][c] = max_path;
    }
};

Example Problem Leetcode 1857. 有向图中最大颜色值

原理： 在一个有向图中，找到一条路径，使得路径上出现次数最多的颜色值最大。

1. 首先，使用拓扑排序检测图中是否有环。如果存在环，则可以无限次经过环上的节点，答案是无穷大（题目规定返回-1）。
2. 定义 dp[u][c] 为到达节点 u 的路径中，颜色 c 出现的最大次数。
3. 在拓扑排序的过程中更新 dp 数组。当从节点 u 移动到邻居 v 时： dp[v][c] = max(dp[v][c], dp[u][c] + (colors[v] == c)) 其中 colors[v] == c 是一个布尔表达式，如果 v 的颜色是 c，则为1，否则为0。
4. 在整个过程中，用一个全局变量记录所有 dp 值的最大值。

#include <vector>
#include <string>
#include <queue>
#include <algorithm>

class Solution {
public:
    int largestPathValue(std::string colors, std::vector<std::vector<int>>& edges) {
        int n = colors.length();
        std::vector<std::vector<int>> graph(n);
        std::vector<int> in_degree(n, 0);
        for (const auto& edge : edges) {
            graph[edge[0]].push_back(edge[1]);
            in_degree[edge[1]]++;
        }

        std::vector<std::vector<int>> dp(n, std::vector<int>(26, 0));
        std::queue<int> q;
        for (int i = 0; i < n; ++i) {
            if (in_degree[i] == 0) {
                q.push(i);
            }
        }

        int max_val = 0;
        int nodes_seen = 0;
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            nodes_seen++;
            
            dp[u][colors[u] - 'a']++;
            max_val = std::max(max_val, dp[u][colors[u] - 'a']);

            for (int v : graph[u]) {
                for (int c = 0; c < 26; ++c) {
                    dp[v][c] = std::max(dp[v][c], dp[u][c]);
                }
                in_degree[v]--;
                if (in_degree[v] == 0) {
                    q.push(v);
                }
            }
        }

        return nodes_seen == n ? max_val : -1;
    }
};

并查集 (Union-Find)#

并查集是一种用于处理不相交集合的合并与查询的数据结构。它主要支持两个操作：

• find(i): 确定元素 i 属于哪个集合。
• union(i, j): 将元素 i 和 j 所在的集合合并。 常用于解决连通性问题，如判断图中两个节点是否连通、计算连通分量数量等。

Example Problem Leetcode 990. 等式方程的可满足性

原理： 这是一个并查集的经典应用。

1. 将所有变量 a 到 z 看作并查集中的元素。
2. 首先遍历所有等式 a==b。对于每个等式，将 a 和 b 所在的集合合并（union）。这表示所有相等的变量都属于同一个连通分量。
3. 然后遍历所有不等式 c!=d。对于每个不等式，检查 c 和 d 是否在同一个集合中（find(c) == find(d)）。如果在，说明 c 和 d 被之前的等式强制要求相等，与当前不等式矛盾，返回 false。
4. 如果所有不等式都不矛盾，返回 true。

#include <vector>
#include <string>

class DSU {
private:
    std::vector<int> parent;
public:
    DSU(int n) {
        parent.resize(n);
        for (int i = 0; i < n; ++i) parent[i] = i;
    }
    int find(int i) {
        if (parent[i] == i) return i;
        return parent[i] = find(parent[i]);
    }
    void unite(int i, int j) {
        int root_i = find(i);
        int root_j = find(j);
        if (root_i != root_j) {
            parent[root_i] = root_j;
        }
    }
};

class Solution {
public:
    bool equationsPossible(std::vector<std::string>& equations) {
        DSU dsu(26);
        for (const std::string& eq : equations) {
            if (eq[1] == '=') {
                dsu.unite(eq[0] - 'a', eq[3] - 'a');
            }
        }
        for (const std::string& eq : equations) {
            if (eq[1] == '!') {
                if (dsu.find(eq[0] - 'a') == dsu.find(eq[3] - 'a')) {
                    return false;
                }
            }
        }
        return true;
    }
};

Example Problem Leetcode 997. 找到小镇的法官

原理： 这是一个简单的图问题，可以通过计算节点的入度和出度来解决。小镇的法官满足两个条件：

1. 所有其他 n-1 个人都信任他，意味着法官的入度是 n-1。
2. 他不信任任何人，意味着法官的出度是 0。 我们可以遍历 trust 数组，用两个数组分别记录每个人的入度和出度，然后找到满足条件的节点。

#include <vector>

class Solution {
public:
    int findJudge(int n, std::vector<std::vector<int>>& trust) {
        if (n == 1) return 1;
        std::vector<int> in_degree(n + 1, 0);
        std::vector<int> out_degree(n + 1, 0);
        
        for (const auto& t : trust) {
            out_degree[t[0]]++;
            in_degree[t[1]]++;
        }
        
        for (int i = 1; i <= n; ++i) {
            if (in_degree[i] == n - 1 && out_degree[i] == 0) {
                return i;
            }
        }
        
        return -1;
    }
};

Example Problem Leetcode 2127. 参加会议的最多员工数

原理： 这是一个功能图（每个节点出度为1）的问题。员工可以形成两种结构来开会：

1. 一个长度大于2的环。
2. 两个相-互喜欢的员工（一个长度为2的环），以及分别指向这两位员工的最长“手臂”链条。

我们可以先用拓扑排序（Kahn算法）剥离出所有的非环部分（树枝），计算出每个节点作为链条末端时的最长链长度。然后，处理剩下的环：

• 对于长度大于2的环，环上所有员工可以一起开会，更新最大值。
• 对于长度为2的环（a <-> b），可以参加会议的人数是 2 + (a的最长手臂) + (b的最长手臂)。

#include <vector>
#include <queue>
#include <algorithm>

class Solution {
public:
    int maximumInvitations(std::vector<int>& favorite) {
        int n = favorite.size();
        std::vector<int> in_degree(n, 0);
        for (int f : favorite) {
            in_degree[f]++;
        }

        std::queue<int> q;
        std::vector<int> max_depth(n, 1);
        for (int i = 0; i < n; ++i) {
            if (in_degree[i] == 0) {
                q.push(i);
            }
        }

        // 拓扑排序，计算非环节点的最长链
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            int v = favorite[u];
            max_depth[v] = std::max(max_depth[v], max_depth[u] + 1);
            in_degree[v]--;
            if (in_degree[v] == 0) {
                q.push(v);
            }
        }

        int max_cycle_len = 0;
        int two_person_chains_sum = 0;
        std::vector<bool> visited(n, false);

        for (int i = 0; i < n; ++i) {
            if (in_degree[i] > 0 && !visited[i]) {
                if (favorite[favorite[i]] == i) { // 长度为2的环
                    two_person_chains_sum += max_depth[i] + max_depth[favorite[i]];
                    visited[i] = visited[favorite[i]] = true;
                } else { // 长度大于2的环
                    int curr = i;
                    int cycle_len = 0;
                    while (!visited[curr]) {
                        visited[curr] = true;
                        cycle_len++;
                        curr = favorite[curr];
                    }
                    max_cycle_len = std::max(max_cycle_len, cycle_len);
                }
            }
        }
        return std::max(max_cycle_len, two_person_chains_sum);
    }
};

图与动态规划#

许多图问题，特别是在网格或DAG上，可以利用动态规划（通常是记忆化搜索）来求解。

Example Problem Leetcode 329. 矩阵中的最长递增路径

原理： 将矩阵看作一个图，每个单元格是一个节点，如果两个相邻单元格的值满足递增关系，则存在一条有向边。问题是求图中的最长路径。这是一个DAG（因为路径必须递增，所以无环），可以用DFS + 记忆化来解决。

1. 定义 dp[r][c] 为从单元格 (r, c) 出发的最长递增路径的长度。
2. 对每个单元格 (r, c) 调用DFS函数。
3. DFS函数中，如果 dp[r][c] 已计算过，直接返回。否则，探索四个方向的邻居 (nr, nc)，如果 matrix[nr][nc] > matrix[r][c]，则 dp[r][c] 可以更新为 1 + dfs(nr, nc)。
4. 取所有方向的最大值更新 dp[r][c]，并用一个全局变量记录所有 dp 值中的最大值。

#include <vector>
#include <algorithm>

class Solution {
public:
    int longestIncreasingPath(std::vector<std::vector<int>>& matrix) {
        if (matrix.empty()) return 0;
        int rows = matrix.size(), cols = matrix[0].size();
        std::vector<std::vector<int>> dp(rows, std::vector<int>(cols, 0));
        int max_len = 0;
        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < cols; ++j) {
                max_len = std::max(max_len, dfs(matrix, i, j, dp));
            }
        }
        return max_len;
    }

private:
    int dfs(const std::vector<std::vector<int>>& matrix, int r, int c, std::vector<std::vector<int>>& dp) {
        if (dp[r][c] != 0) return dp[r][c];
        
        int max_path = 1;
        int rows = matrix.size(), cols = matrix[0].size();
        int dr[] = {-1, 1, 0, 0};
        int dc[] = {0, 0, -1, 1};
        
        for (int i = 0; i < 4; ++i) {
            int nr = r + dr[i];
            int nc = c + dc[i];
            if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && matrix[nr][nc] > matrix[r][c]) {
                max_path = std::max(max_path, 1 + dfs(matrix, nr, nc, dp));
            }
        }
        
        return dp[r][c] = max_path;
    }
};

Example Problem Leetcode 1857. 有向图中最大颜色值

原理： 在一个有向图中，找到一条路径，使得路径上出现次数最多的颜色值最大。

1. 首先，使用拓扑排序检测图中是否有环。如果存在环，则可以无限次经过环上的节点，答案是无穷大（题目规定返回-1）。
2. 定义 dp[u][c] 为到达节点 u 的路径中，颜色 c 出现的最大次数。
3. 在拓扑排序的过程中更新 dp 数组。当从节点 u 移动到邻居 v 时： dp[v][c] = max(dp[v][c], dp[u][c] + (colors[v] == c)) 其中 colors[v] == c 是一个布尔表达式，如果 v 的颜色是 c，则为1，否则为0。
4. 在整个过程中，用一个全局变量记录所有 dp 值的最大值。

#include <vector>
#include <string>
#include <queue>
#include <algorithm>

class Solution {
public:
    int largestPathValue(std::string colors, std::vector<std::vector<int>>& edges) {
        int n = colors.length();
        std::vector<std::vector<int>> graph(n);
        std::vector<int> in_degree(n, 0);
        for (const auto& edge : edges) {
            graph[edge[0]].push_back(edge[1]);
            in_degree[edge[1]]++;
        }

        std::vector<std::vector<int>> dp(n, std::vector<int>(26, 0));
        std::queue<int> q;
        for (int i = 0; i < n; ++i) {
            if (in_degree[i] == 0) {
                q.push(i);
            }
        }

        int max_val = 0;
        int nodes_seen = 0;
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            nodes_seen++;
            
            dp[u][colors[u] - 'a']++;
            max_val = std::max(max_val, dp[u][colors[u] - 'a']);

            for (int v : graph[u]) {
                for (int c = 0; c < 26; ++c) {
                    dp[v][c] = std::max(dp[v][c], dp[u][c]);
                }
                in_degree[v]--;
                if (in_degree[v] == 0) {
                    q.push(v);
                }
            }
        }

        return nodes_seen == n ? max_val : -1;
    }
};

并查集 (Union-Find)#

并查集是一种用于处理不相交集合的合并与查询的数据结构。它主要支持两个操作：

• find(i): 确定元素 i 属于哪个集合。
• union(i, j): 将元素 i 和 j 所在的集合合并。 常用于解决连通性问题，如判断图中两个节点是否连通、计算连通分量数量等。

Example Problem Leetcode 990. 等式方程的可满足性

原理： 这是一个并查集的经典应用。

1. 将所有变量 a 到 z 看作并查集中的元素。
2. 首先遍历所有等式 a==b。对于每个等式，将 a 和 b 所在的集合合并（union）。这表示所有相等的变量都属于同一个连通分量。
3. 然后遍历所有不等式 c!=d。对于每个不等式，检查 c 和 d 是否在同一个集合中（find(c) == find(d)）。如果在，说明 c 和 d 被之前的等式强制要求相等，与当前不等式矛盾，返回 false。
4. 如果所有不等式都不矛盾，返回 true。

#include <vector>
#include <string>

class DSU {
private:
    std::vector<int> parent;
public:
    DSU(int n) {
        parent.resize(n);
        for (int i = 0; i < n; ++i) parent[i] = i;
    }
    int find(int i) {
        if (parent[i] == i) return i;
        return parent[i] = find(parent[i]);
    }
    void unite(int i, int j) {
        int root_i = find(i);
        int root_j = find(j);
        if (root_i != root_j) {
            parent[root_i] = root_j;
        }
    }
};

class Solution {
public:
    bool equationsPossible(std::vector<std::string>& equations) {
        DSU dsu(26);
        for (const std::string& eq : equations) {
            if (eq[1] == '=') {
                dsu.unite(eq[0] - 'a', eq[3] - 'a');
            }
        }
        for (const std::string& eq : equations) {
            if (eq[1] == '!') {
                if (dsu.find(eq[0] - 'a') == dsu.find(eq[3] - 'a')) {
                    return false;
                }
            }
        }
        return true;
    }
};

Example Problem Leetcode 997. 找到小镇的法官

原理： 这是一个简单的图问题，可以通过计算节点的入度和出度来解决。小镇的法官满足两个条件：

1. 所有其他 n-1 个人都信任他，意味着法官的入度是 n-1。
2. 他不信任任何人，意味着法官的出度是 0。 我们可以遍历 trust 数组，用两个数组分别记录每个人的入度和出度，然后找到满足条件的节点。

#include <vector>

class Solution {
public:
    int findJudge(int n, std::vector<std::vector<int>>& trust) {
        if (n == 1) return 1;
        std::vector<int> in_degree(n + 1, 0);
        std::vector<int> out_degree(n + 1, 0);
        
        for (const auto& t : trust) {
            out_degree[t[0]]++;
            in_degree[t[1]]++;
        }
        
        for (int i = 1; i <= n; ++i) {
            if (in_degree[i] == n - 1 && out_degree[i] == 0) {
                return i;
            }
        }
        
        return -1;
    }
};

Example Problem Leetcode 2127. 参加会议的最多员工数

原理： 这是一个功能图（每个节点出度为1）的问题。员工可以形成两种结构来开会：

1. 一个长度大于2的环。
2. 两个相-互喜欢的员工（一个长度为2的环），以及分别指向这两位员工的最长“手臂”链条。

我们可以先用拓扑排序（Kahn算法）剥离出所有的非环部分（树枝），计算出每个节点作为链条末端时的最长链长度。然后，处理剩下的环：

• 对于长度大于2的环，环上所有员工可以一起开会，更新最大值。
• 对于长度为2的环（a <-> b），可以参加会议的人数是 2 + (a的最长手臂) + (b的最长手臂)。

#include <vector>
#include <queue>
#include <algorithm>

class Solution {
public:
    int maximumInvitations(std::vector<int>& favorite) {
        int n = favorite.size();
        std::vector<int> in_degree(n, 0);
        for (int f : favorite) {
            in_degree[f]++;
        }

        std::queue<int> q;
        std::vector<int> max_depth(n, 1);
        for (int i = 0; i < n; ++i) {
            if (in_degree[i] == 0) {
                q.push(i);
            }
        }

        // 拓扑排序，计算非环节点的最长链
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            int v = favorite[u];
            max_depth[v] = std::max(max_depth[v], max_depth[u] + 1);
            in_degree[v]--;
            if (in_degree[v] == 0) {
                q.push(v);
            }
        }

        int max_cycle_len = 0;
        int two_person_chains_sum = 0;
        std::vector<bool> visited(n, false);

        for (int i = 0; i < n; ++i) {
            if (in_degree[i] > 0 && !visited[i]) {
                if (favorite[favorite[i]] == i) { // 长度为2的环
                    two_person_chains_sum += max_depth[i] + max_depth[favorite[i]];
                    visited[i] = visited[favorite[i]] = true;
                } else { // 长度大于2的环
                    int curr = i;
                    int cycle_len = 0;
                    while (!visited[curr]) {
                        visited[curr] = true;
                        cycle_len++;
                        curr = favorite[curr];
                    }
                    max_cycle_len = std::max(max_cycle_len, cycle_len);
                }
            }
        }
        return std::max(max_cycle_len, two_person_chains_sum);
    }
};

图与动态规划#

许多图问题，特别是在网格或DAG上，可以利用动态规划（通常是记忆化搜索）来求解。

Example Problem Leetcode 329. 矩阵中的最长递增路径

原理： 将矩阵看作一个图，每个单元格是一个节点，如果两个相邻单元格的值满足递增关系，则存在一条有向边。问题是求图中的最长路径。这是一个DAG（因为路径必须递增，所以无环），可以用DFS + 记忆化来解决。

1. 定义 dp[r][c] 为从单元格 (r, c) 出发的最长递增路径的长度。
2. 对每个单元格 (r, c) 调用DFS函数。
3. DFS函数中，如果 dp[r][c] 已计算过，直接返回。否则，探索四个方向的邻居 (nr, nc)，如果 matrix[nr][nc] > matrix[r][c]，则 dp[r][c] 可以更新为 1 + dfs(nr, nc)。
4. 取所有方向的最大值更新 dp[r][c]，并用一个全局变量记录所有 dp 值中的最大值。

#include <vector>
#include <algorithm>

class Solution {
public:
    int longestIncreasingPath(std::vector<std::vector<int>>& matrix) {
        if (matrix.empty()) return 0;
        int rows = matrix.size(), cols = matrix[0].size();
        std::vector<std::vector<int>> dp(rows, std::vector<int>(cols, 0));
        int max_len = 0;
        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < cols; ++j) {
                max_len = std::max(max_len, dfs(matrix, i, j, dp));
            }
        }
        return max_len;
    }

private:
    int dfs(const std::vector<std::vector<int>>& matrix, int r, int c, std::vector<std::vector<int>>& dp) {
        if (dp[r][c] != 0) return dp[r][c];
        
        int max_path = 1;
        int rows = matrix.size(), cols = matrix[0].size();
        int dr[] = {-1, 1, 0, 0};
        int dc[] = {0, 0, -1, 1};
        
        for (int i = 0; i < 4; ++i) {
            int nr = r + dr[i];
            int nc = c + dc[i];
            if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && matrix[nr][nc] > matrix[r][c]) {
                max_path = std::max(max_path, 1 + dfs(matrix, nr, nc, dp));
            }
        }
        
        return dp[r][c] = max_path;
    }
};

Example Problem Leetcode 1857. 有向图中最大颜色值

原理： 在一个有向图中，找到一条路径，使得路径上出现次数最多的颜色值最大。

1. 首先，使用拓扑排序检测图中是否有环。如果存在环，则可以无限次经过环上的节点，答案是无穷大（题目规定返回-1）。
2. 定义 dp[u][c] 为到达节点 u 的路径中，颜色 c 出现的最大次数。
3. 在拓扑排序的过程中更新 dp 数组。当从节点 u 移动到邻居 v 时： dp[v][c] = max(dp[v][c], dp[u][c] + (colors[v] == c)) 其中 colors[v] == c 是一个布尔表达式，如果 v 的颜色是 c，则为1，否则为0。
4. 在整个过程中，用一个全局变量记录所有 dp 值的最大值。

#include <vector>
#include <string>
#include <queue>
#include <algorithm>

class Solution {
public:
    int largestPathValue(std::string colors, std::vector<std::vector<int>>& edges) {
        int n = colors.length();
        std::vector<std::vector<int>> graph(n);
        std::vector<int> in_degree(n, 0);
        for (const auto& edge : edges) {
            graph[edge[0]].push_back(edge[1]);
            in_degree[edge[1]]++;
        }

        std::vector<std::vector<int>> dp(n, std::vector<int>(26, 0));
        std::queue<int> q;
        for (int i = 0; i < n; ++i) {
            if (in_degree[i] == 0) {
                q.push(i);
            }
        }

        int max_val = 0;
        int nodes_seen = 0;
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            nodes_seen++;
            
            dp[u][colors[u] - 'a']++;
            max_val = std::max(max_val, dp[u][colors[u] - 'a']);

            for (int v : graph[u]) {
                for (int c = 0; c < 26; ++c) {
                    dp[v][c] = std::max(dp[v][c], dp[u][c]);
                }
                in_degree[v]--;
                if (in_degree[v] == 0) {
                    q.push(v);
                }
            }
        }

        return nodes_seen == n ? max_val : -1;
    }
};

Example Problem Leetcode 1632. 矩阵转换后的秩

原理： 这是一个结合了并查集和拓扑排序的复杂问题。

1. 分组：将矩阵中所有值相同的单元格按值分组，并按值从小到大处理。
2. 处理同行同列：对于每个值，遍历其所有出现位置。使用并查集将同一行或同一列的单元格合并到同一个连通分量中。这意味着它们必须有相同的秩。
3. 计算组的秩：对于每个连通分量（组），其秩必须大于等于该组内所有单元格所在行和列的当前最大秩。所以，组的秩 group_rank = 1 + max(rank_row[r], rank_col[c]) for all (r, c) in the group。
4. 更新秩：计算出组的秩后，用这个新秩更新该组内所有单元格的最终秩，并同时更新这些单元格所在行和列的 rank_row 和 rank_col。

#include <vector>
#include <map>
#include <algorithm>
#include <numeric>

class DSU_Rank {
public:
    std::vector<int> parent;
    DSU_Rank(int n) {
        parent.resize(n);
        std::iota(parent.begin(), parent.end(), 0);
    }
    int find(int i) {
        if (parent[i] == i) return i;
        return parent[i] = find(parent[i]);
    }
    void unite(int i, int j) {
        int root_i = find(i);
        int root_j = find(j);
        if (root_i != root_j) parent[root_i] = root_j;
    }
};

class Solution {
public:
    std::vector<std::vector<int>> matrixRankTransform(std::vector<std::vector<int>>& matrix) {
        int rows = matrix.size(), cols = matrix[0].size();
        std::vector<int> rank_row(rows, 0), rank_col(cols, 0);
        DSU_Rank dsu(rows * cols);

        // Step 1: Group by value
        std::vector<std::tuple<int, int, int, int>> cells;
        for (int r = 0; r < rows; ++r) {
            for (int c = 0; c < cols; ++c) {
                cells.emplace_back(matrix[r][c], r, c, r * cols + c);
            }
        }
        std::sort(cells.begin(), cells.end());

        // Step 2: Union-Find for rows and columns
        for (auto& [value, r, c, id] : cells) {
            if (r > 0 && matrix[r - 1][c] == value) {
                dsu.unite(id, (r - 1) * cols + c);
            }
            if (c > 0 && matrix[r][c - 1] == value) {
                dsu.unite(id, r * cols + c - 1);
            }
        }

        // Step 3: Calculate rank for each group
        std::map<int, int> group_rank;
        for (int r = 0; r < rows; ++r) {
            for (int c = 0; c < cols; ++c) {
                int root = dsu.find(r * cols + c);
                group_rank[root] = std::max(group_rank[root], std::max(rank_row[r], rank_col[c]));
            }
        }

        // Step 4: Assign ranks
        for (int r = 0; r < rows; ++r) {
            for (int c = 0; c < cols; ++c) {
                int root = dsu.find(r * cols + c);
                int new_rank = group_rank[root] + 1;
                rank_row[r] = rank_col[c] = new_rank;
            }
        }

        // Prepare the result
        std::vector<std::vector<int>> ans(rows, std::vector<int>(cols));
        for (int r = 0; r < rows; ++r) {
            for (int c = 0; c < cols; ++c) {
                ans[r][c] = std::max(rank_row[r], rank_col[c]);
            }
        }
        return ans;
    }
};

最短路径#

最短路径算法用于寻找图中两点之间成本最低的路径。

#include <vector>
#include <queue>

using ll = long long;
const ll INF = 1e18;

class Solution {
public:
    int countPaths(int n, std::vector<std::vector<int>>& roads) {
        std::vector<std::vector<std::pair<int, int>>> graph(n);
        for (const auto& road : roads) {
            graph[road[0]].push_back({road[1], road[2]});
            graph[road[1]].push_back({road[0], road[2]});
        }
        
        std::vector<ll> dist(n, INF);
        std::vector<ll> ways(n, 0);
        dist[0] = 0;
        ways[0] = 1;
        
        std::priority_queue<std::pair<ll, int>, std::vector<std::pair<ll, int>>, std::greater<std::pair<ll, int>>> pq;
        pq.push({0, 0}); // {distance, node}
        
        int MOD = 1e9 + 7;
        
        while (!pq.empty()) {
            auto [d, u] = pq.top();
            pq.pop();
            
            if (d > dist[u]) continue;
            
            for (auto& edge : graph[u]) {
                int v = edge.first;
                int weight = edge.second;
                if (dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight;
                    ways[v] = ways[u];
                    pq.push({dist[v], v});
                } else if (dist[u] + weight == dist[v]) {
                    ways[v] = (ways[v] + ways[u]) % MOD;
                }
            }
        }
        
        return ways[n - 1];
    }
};

#include <vector>
#include <queue>
#include <map>
#include <cmath>

using ll = long long;

class Solution {
public:
    int minimumCost(std::vector<int>& start, std::vector<int>& target, std::vector<std::vector<int>>& specialRoads) {
        std::map<std::pair<int, int>, ll> dist;
        dist[{start[0], start[1]}] = 0;
        
        std::priority_queue<std::pair<ll, std::pair<int, int>>, std::vector<std::pair<ll, std::pair<int, int>>>, std::greater<>> pq;
        pq.push({0, {start[0], start[1]}});

        ll min_cost = abs(start[0] - target[0]) + abs(start[1] - target[1]);

        while (!pq.empty()) {
            auto [d, p] = pq.top();
            pq.pop();
            int r = p.first, c = p.second;

            if (d > dist[{r, c}]) continue;

            min_cost = std::min(min_cost, d + (ll)abs(r - target[0]) + (ll)abs(c - target[1]));

            for (const auto& road : specialRoads) {
                int r1 = road[0], c1 = road[1], r2 = road[2], c2 = road[3], cost = road[4];
                ll new_dist = d + (ll)abs(r - r1) + (ll)abs(c - c1) + cost;
                
                if (!dist.count({r2, c2}) || new_dist < dist[{r2, c2}]) {
                    dist[{r2, c2}] = new_dist;
                    pq.push({new_dist, {r2, c2}});
                }
            }
        }
        return min_cost;
    }
};

#include <vector>
#include <queue>

using ll = long long;
const ll INF_SP = 1e18;

class Solution {
public:
    std::vector<bool> findAnswer(int n, std::vector<std::vector<int>>& edges) {
        std::vector<std::vector<std::pair<int, int>>> graph(n);
        for (const auto& edge : edges) {
            graph[edge[0]].push_back({edge[1], edge[2]});
            graph[edge[1]].push_back({edge[0], edge[2]});
        }

        auto dijkstra = [&](int start_node) {
            std::vector<ll> dist(n, INF_SP);
            dist[start_node] = 0;
            std::priority_queue<std::pair<ll, int>, std::vector<std::pair<ll, int>>, std::greater<>> pq;
            pq.push({0, start_node});
            while (!pq.empty()) {
                auto [d, u] = pq.top();
                pq.pop();
                if (d > dist[u]) continue;
                for (auto& edge : graph[u]) {
                    int v = edge.first;
                    int w = edge.second;
                    if (dist[u] + w < dist[v]) {
                        dist[v] = dist[u] + w;
                        pq.push({dist[v], v});
                    }
                }
            }
            return dist;
        };

        std::vector<ll> dist_start = dijkstra(0);
        std::vector<ll> dist_end = dijkstra(n - 1);

        std::vector<bool> ans(edges.size(), false);
        if (dist_start[n - 1] >= INF_SP) return ans;

        for (int i = 0; i < edges.size(); ++i) {
            int u = edges[i][0], v = edges[i][1], w = edges[i][2];
            if (dist_start[u] + w + dist_end[v] == dist_start[n - 1]) {
                ans[i] = true;
            }
            if (dist_start[v] + w + dist_end[u] == dist_start[n - 1]) {
                ans[i] = true;
            }
        }
        return ans;
    }
};

#include <vector>
#include <string>
#include <algorithm>

using ll = long long;

class Solution {
public:
    long long minimumCost(std::string source, std::string target, std::vector<char>& original, std::vector<char>& changed, std::vector<int>& cost) {
        const ll INF = 1e12;
        std::vector<std::vector<ll>> min_cost(26, std::vector<ll>(26, INF));

        for (int i = 0; i < 26; ++i) min_cost[i][i] = 0;

        for (size_t i = 0; i < original.size(); ++i) {
            int u = original[i] - 'a';
            int v = changed[i] - 'a';
            min_cost[u][v] = std::min(min_cost[u][v], (ll)cost[i]);
        }

        // Floyd-Warshall
        for (int k = 0; k < 26; ++k) {
            for (int i = 0; i < 26; ++i) {
                for (int j = 0; j < 26; ++j) {
                    min_cost[i][j] = std::min(min_cost[i][j], min_cost[i][k] + min_cost[k][j]);
                }
            }
        }

        ll total_cost = 0;
        for (size_t i = 0; i < source.length(); ++i) {
            int u = source[i] - 'a';
            int v = target[i] - 'a';
            if (min_cost[u][v] >= INF) {
                return -1;
            }
            total_cost += min_cost[u][v];
        }

        return total_cost;
    }
};

#include <vector>
#include <string>
#include <algorithm>
#include <map>
#include <set>

using ll = long long;

class Solution {
public:
    long long minimumCost(std::string source, std::string target, std::vector<std::string>& original, std::vector<std::string>& changed, std::vector<int>& cost) {
        const ll INF = 1e12;
        std::map<std::string, int> node_map;
        int next_node_id = 0;

        auto get_node_id = [&](const std::string& s) {
            if (node_map.find(s) == node_map.end()) {
                node_map[s] = next_node_id++;
            }
            return node_map[s];
        };

        for (const auto& s : original) get_node_id(s);
        for (const auto& s : changed) get_node_id(s);

        int num_nodes = next_node_id;
        std::vector<std::vector<ll>> adj(num_nodes, std::vector<ll>(num_nodes, INF));
        for(int i = 0; i < num_nodes; ++i) adj[i][i] = 0;

        for (size_t i = 0; i < original.size(); ++i) {
            int u = get_node_id(original[i]);
            int v = get_node_id(changed[i]);
            adj[u][v] = std::min(adj[u][v], (ll)cost[i]);
        }

        for (int k = 0; k < num_nodes; ++k) {
            for (int i = 0; i < num_nodes; ++i) {
                for (int j = 0; j < num_nodes; ++j) {
                    if (adj[i][k] < INF && adj[k][j] < INF) {
                        adj[i][j] = std::min(adj[i][j], adj[i][k] + adj[k][j]);
                    }
                }
            }
        }

        int n = source.length();
        std::vector<ll> dp(n + 1, INF);
        dp[0] = 0;

        for (int i = 0; i < n; ++i) {
            if (dp[i] >= INF) continue;
            
            // Case 1: Characters match
            if (source[i] == target[i]) {
                dp[i + 1] = std::min(dp[i + 1], dp[i]);
            }

            // Case 2: Substring conversion
            for (auto const& [s_orig, id_orig] : node_map) {
                int len = s_orig.length();
                if (i + len > n) continue;
                if (source.substr(i, len) == s_orig) {
                    for (auto const& [s_chg, id_chg] : node_map) {
                        if (s_chg.length() != len) continue;
                        if (target.substr(i, len) == s_chg) {
                            if (adj[id_orig][id_chg] < INF) {
                                dp[i + len] = std::min(dp[i + len], dp[i] + adj[id_orig][id_chg]);
                            }
                        }
                    }
                }
            }
        }

        return dp[n] >= INF ? -1 : dp[n];
    }
};

最小生成树 (MST)#

最小生成树是在一个连通的、带权无向图中，找到一棵包含所有顶点的树，使得树的所有边的权重之和最小。

#include <vector>
#include <cmath>
#include <algorithm>
#include <numeric>

class DSU_MST {
private:
    std::vector<int> parent;
public:
    DSU_MST(int n) {
        parent.resize(n);
        std::iota(parent.begin(), parent.end(), 0);
    }
    int find(int i) {
        if (parent[i] == i) return i;
        return parent[i] = find(parent[i]);
    }
    bool unite(int i, int j) {
        int root_i = find(i);
        int root_j = find(j);
        if (root_i != root_j) {
            parent[root_i] = root_j;
            return true;
        }
        return false;
    }
};

struct Edge {
    int u, v, weight;
};

bool compareEdges(const Edge& a, const Edge& b) {
    return a.weight < b.weight;
}

class Solution {
public:
    int minCostConnectPoints(std::vector<std::vector<int>>& points) {
        int n = points.size();
        if (n <= 1) return 0;
        
        std::vector<Edge> edges;
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                int dist = std::abs(points[i][0] - points[j][0]) + std::abs(points[i][1] - points[j][1]);
                edges.push_back({i, j, dist});
            }
        }
        
        std::sort(edges.begin(), edges.end(), compareEdges);
        
        DSU_MST dsu(n);
        int total_cost = 0;
        int edges_count = 0;
        
        for (const auto& edge : edges) {
            if (dsu.unite(edge.u, edge.v)) {
                total_cost += edge.weight;
                edges_count++;
                if (edges_count == n - 1) break;
            }
        }
        
        return total_cost;
    }
};

#include <vector>
#include <algorithm>
#include <numeric>

class DSU_Kruskal {
public:
    std::vector<int> parent;
    int components;
    DSU_Kruskal(int n) {
        parent.resize(n);
        std::iota(parent.begin(), parent.end(), 0);
        components = n;
    }
    int find(int i) {
        if (parent[i] == i) return i;
        return parent[i] = find(parent[i]);
    }
    bool unite(int i, int j) {
        int root_i = find(i);
        int root_j = find(j);
        if (root_i != root_j) {
            parent[root_i] = root_j;
            components--;
            return true;
        }
        return false;
    }
};

class Solution {
public:
    std::vector<std::vector<int>> findCriticalAndPseudoCriticalEdges(int n, std::vector<std::vector<int>>& edges) {
        for (int i = 0; i < edges.size(); ++i) {
            edges[i].push_back(i); // Store original index
        }
        std::sort(edges.begin(), edges.end(), [](const auto& a, const auto& b) {
            return a[2] < b[2];
        });

        auto get_mst_weight = [&](int n, const auto& current_edges, int excluded_idx = -1, int included_idx = -1) {
            DSU_Kruskal dsu(n);
            int weight = 0;
            int edges_count = 0;

            if (included_idx != -1) {
                weight += edges[included_idx][2];
                dsu.unite(edges[included_idx][0], edges[included_idx][1]);
                edges_count++;
            }

            for (int i = 0; i < current_edges.size(); ++i) {
                if (i == excluded_idx || i == included_idx) continue;
                const auto& edge = current_edges[i];
                if (dsu.unite(edge[0], edge[1])) {
                    weight += edge[2];
                    edges_count++;
                }
            }
            return (edges_count == n - 1) ? weight : INT_MAX;
        };

        int original_mst_weight = get_mst_weight(n, edges);
        
        std::vector<int> critical, pseudo_critical;
        for (int i = 0; i < edges.size(); ++i) {
            // Check for critical edge
            int weight_without = get_mst_weight(n, edges, i);
            if (weight_without > original_mst_weight) {
                critical.push_back(edges[i][3]);
                continue;
            }
            
            // Check for pseudo-critical edge
            int weight_with = get_mst_weight(n, edges, -1, i);
            if (weight_with == original_mst_weight) {
                pseudo_critical.push_back(edges[i][3]);
            }
        }
        
        return {critical, pseudo_critical};
    }
};