Hard

题目描述

给定一个有 n 个顶点的加权无向连通图（顶点编号从 0 到 n-1），以及一个边数组 edges，其中 edges[i] = [ai, bi, weighti] 表示连接顶点 ai 和 bi 的双向加权边，权重为 weighti。

最小生成树（MST）是图中连接所有顶点且无环的边的子集，具有最小的总边权重。

找出给定图的最小生成树中的所有关键边和伪关键边。如果从图中删除某条 MST 边会导致 MST 权重增加，则该边是关键边。另一方面，伪关键边是可能出现在某些 MST 中但不是所有 MST 中的边。

注意，你可以按任意顺序返回边的索引。

示例 1：

输入：n = 5, edges = [[0,1,1],[1,2,1],[2,3,2],[0,3,2],[0,4,3],[3,4,3],[1,4,6]]
输出：[[0,1],[2,3,4,5]]
解释：边 0 和 1 出现在所有 MST 中，因此是关键边。边 2、3、4、5 只在某些 MST 中出现，因此是伪关键边。

示例 2：

输入：n = 4, edges = [[0,1,1],[1,2,1],[2,3,1],[0,3,1]]
输出：[[],[0,1,2,3]]
解释：由于所有 4 条边的权重相等，从给定的 4 条边中选择任意 3 条边都会产生 MST。因此所有 4 条边都是伪关键边。

约束条件：

  • 2 <= n <= 100
  • 1 <= edges.length <= min(200, n * (n - 1) / 2)
  • edges[i].length == 3
  • 0 <= ai < bi < n
  • 1 <= weighti <= 1000
  • 所有的 (ai, bi) 都是不同的。

解题思路

这道题需要我们找出最小生成树中的关键边和伪关键边。我们可以使用 Kruskal 算法和并查集来解决。

核心思路：

  1. 计算原始 MST 权重：使用 Kruskal 算法计算完整图的 MST 权重作为基准。

  2. 判断关键边：对于每条边，如果删除它后重新计算 MST，权重增加或无法形成连通图，则该边是关键边。

  3. 判断伪关键边：对于非关键边，强制包含该边并计算 MST，如果权重与原始 MST 相同，则该边是伪关键边。

算法步骤：

  • 为边数组添加索引信息，按权重排序
  • 实现并查集用于 Kruskal 算法
  • 计算原始 MST 权重
  • 逐个测试每条边：
    • 删除该边，计算新 MST 权重判断是否为关键边
    • 如果不是关键边，强制包含该边计算 MST 权重判断是否为伪关键边

时间复杂度分析： 对于每条边，我们需要运行两次 Kruskal 算法（删除和强制包含），每次 Kruskal 的时间复杂度是 O(E log E)，总共有 E 条边，所以总时间复杂度是 O(E² log E)。

代码实现

class Solution {
public:
    class UnionFind {
    public:
        vector<int> parent, rank;
        int components;
        
        UnionFind(int n) : parent(n), rank(n, 0), components(n) {
            iota(parent.begin(), parent.end(), 0);
        }
        
        int find(int x) {
            return parent[x] == x ? x : parent[x] = find(parent[x]);
        }
        
        bool unite(int x, int y) {
            int px = find(x), py = find(y);
            if (px == py) return false;
            if (rank[px] < rank[py]) swap(px, py);
            parent[py] = px;
            if (rank[px] == rank[py]) rank[px]++;
            components--;
            return true;
        }
        
        bool connected() { return components == 1; }
    };
    
    int kruskal(int n, vector<vector<int>>& sortedEdges, int skipEdge, int forceEdge) {
        UnionFind uf(n);
        int weight = 0, edgesUsed = 0;
        
        if (forceEdge != -1) {
            auto& edge = sortedEdges[forceEdge];
            if (uf.unite(edge[0], edge[1])) {
                weight += edge[2];
                edgesUsed++;
            }
        }
        
        for (int i = 0; i < sortedEdges.size(); i++) {
            if (i == skipEdge || i == forceEdge) continue;
            auto& edge = sortedEdges[i];
            if (uf.unite(edge[0], edge[1])) {
                weight += edge[2];
                edgesUsed++;
                if (edgesUsed == n - 1) break;
            }
        }
        
        return uf.connected() ? weight : INT_MAX;
    }
    
    vector<vector<int>> findCriticalAndPseudoCriticalEdges(int n, vector<vector<int>>& edges) {
        vector<vector<int>> indexedEdges;
        for (int i = 0; i < edges.size(); i++) {
            indexedEdges.push_back({edges[i][0], edges[i][1], edges[i][2], i});
        }
        
        sort(indexedEdges.begin(), indexedEdges.end(), 
             [](const vector<int>& a, const vector<int>& b) { return a[2] < b[2]; });
        
        int originalWeight = kruskal(n, indexedEdges, -1, -1);
        
        vector<int> critical, pseudoCritical;
        
        for (int i = 0; i < indexedEdges.size(); i++) {
            if (kruskal(n, indexedEdges, i, -1) > originalWeight) {
                critical.push_back(indexedEdges[i][3]);
            } else if (kruskal(n, indexedEdges, -1, i) == originalWeight) {
                pseudoCritical.push_back(indexedEdges[i][3]);
            }
        }
        
        return {critical, pseudoCritical};
    }
};

class Solution:
    def findCriticalAndPseudoCriticalEdges(self, n: int, edges: List[List[int]]) -> List[List[int]]:
        class UnionFind:
            def __init__(self, n):
                self.parent = list(range(n))
                self.rank = [0] * n
                self.components = n
            
            def find(self, x):
                if self.parent[x] != x:
                    self.parent[x] = self.find(self.parent[x])
                return self.parent[x]
            
            def union(self, x, y):
                px, py = self.find(x), self.find(y)
                if px == py:
                    return False
                if self.rank[px] < self.rank[py]:
                    px, py = py, px
                self.parent[py] = px
                if self.rank[px] == self.rank[py]:
                    self.rank[px] += 1
                self.components -= 1
                return True
            
            def connected(self):
                return self.components == 1
        
        def kruskal(skip_edge, force_edge):
            uf = UnionFind(n)
            weight = 0
            edges_used = 0
            
            if force_edge != -1:
                edge = indexed_edges[force_edge]
                if uf.union(edge[0], edge[1]):
                    weight += edge[2]
                    edges_used += 1
            
            for i, edge in enumerate(indexed_edges):
                if i == skip_edge or i == force_edge:
                    continue
                if uf.union(edge[0], edge[1]):
                    weight += edge[2]
                    edges_used += 1
                    if edges_used == n - 1:
                        break
            
            return weight if uf.connected() else float('inf')
        
        indexed_edges = [edge + [i] for i, edge in enumerate(edges)]
        indexed_edges.sort(key=lambda x: x[2])
        
        original_weight = kruskal(-1, -1)
        
        critical = []
        pseudo_critical = []
        
        for i in range(len(indexed_edges)):
            if kruskal(i, -1) > original_weight:
                critical.append(indexed_edges[i][3])
            elif kruskal(-1, i) == original_weight:
                pseudo_critical.append(indexed_edges[i][3])
        
        return [critical, pseudo_critical]

public class Solution {
    public class UnionFind {
        private int[] parent, rank;
        public int components;
        
        public UnionFind(int n) {
            parent = new int[n];
            rank = new int[n];
            components = n;
            for (int i = 0; i < n; i++) parent[i] = i;
        }
        
        public int Find(int x) {
            return parent[x] == x ? x : parent[x] = Find(parent[x]);
        }
        
        public bool Union(int x, int y) {
            int px = Find(x), py = Find(y);
            if (px == py) return false;
            if (rank[px] < rank[py]) {
                int temp = px; px = py; py = temp;
            }
            parent[py] = px;
            if (rank[px] == rank[py]) rank[px]++;
            components--;
            return true;
        }
        
        public bool Connected() => components == 1;
    }
    
    private int Kruskal(int n, int[][] sortedEdges, int skipEdge, int forceEdge) {
        var uf = new UnionFind(n);
        int weight = 0, edgesUsed = 0;
        
        if (forceEdge != -1) {
            var edge = sortedEdges[forceEdge];
            if (uf.Union(edge[0], edge[1])) {
                weight += edge[2];
                edgesUsed++;
            }
        }
        
        for (int i = 0; i < sortedEdges.Length; i++) {
            if (i == skipEdge || i == forceEdge) continue;
            var edge = sortedEdges[i];
            if (uf.Union(edge[0], edge[1])) {
                weight += edge[2];
                edgesUsed++;
                if (edgesUsed == n - 1) break;
            }
        }
        
        return uf.Connected() ? weight : int.MaxValue;
    }
    
    public IList<IList<int>> FindCriticalAndPseudoCriticalEdges(int n, int[][] edges) {
        var indexedEdges = new int[edges.Length][];
        for (int i = 0; i < edges.Length; i++) {
            indexedEdges[i] = new int[] { edges[i][0], edges[i][1], edges[i][2], i };
        }
        
        Array.Sort(indexedEdges, (a, b) => a[2].CompareTo(b[2]));
        
        int originalWeight = Kruskal(n, indexedEdges, -1, -1);
        
        var critical = new List<int>();
        var pseudoCritical = new List<int>();
        
        for (int i = 0; i < indexedEdges.Length; i++) {
            if (Kruskal(n, indexedEdges, i, -1) > originalWeight) {
                critical.Add(indexedEdges[i][3]);
            } else if (Kruskal(n, indexedEdges, -1, i) == originalWeight) {
                pseudoCritical.Add(indexedEdges[i][3]);
            }
        }
        
        return new List<IList<int>> { critical, pseudoCritical };
    }
}

var findCriticalAndPseudoCriticalEdges = function(n, edges) {
    // Add index to each edge for tracking
    const indexedEdges = edges.map((edge, i) => [...edge, i]);
    
    // Sort edges by weight for Kruskal's algorithm
    indexedEdges.sort((a, b) => a[2] - b[2]);
    
    // Union-Find class
    class UnionFind {
        constructor(n) {
            this.parent = Array.from({length: n}, (_, i) => i);
            this.rank = new Array(n).fill(0);
            this.components = n;
        }
        
        find(x) {
            if (this.parent[x] !== x) {
                this.parent[x] = this.find(this.parent[x]);
            }
            return this.parent[x];
        }
        
        union(x, y) {
            const px = this.find(x);
            const py = this.find(y);
            
            if (px === py) return false;
            
            if (this.rank[px] < this.rank[py]) {
                this.parent[px] = py;
            } else if (this.rank[px] > this.rank[py]) {
                this.parent[py] = px;
            } else {
                this.parent[py] = px;
                this.rank[px]++;
            }
            
            this.components--;
            return true;
        }
        
        isConnected() {
            return this.components === 1;
        }
    }
    
    // Function to calculate MST weight
    function getMSTWeight(excludeEdge = -1, includeEdge = -1) {
        const uf = new UnionFind(n);
        let weight = 0;
        let edgesUsed = 0;
        
        // Include forced edge first if specified
        if (includeEdge !== -1) {
            const [u, v, w] = indexedEdges[includeEdge];
            if (uf.union(u, v)) {
                weight += w;
                edgesUsed++;
            }
        }
        
        // Process all other edges
        for (let i = 0; i < indexedEdges.length; i++) {
            if (i === excludeEdge || i === includeEdge) continue;
            
            const [u, v, w] = indexedEdges[i];
            if (uf.union(u, v)) {
                weight += w;
                edgesUsed++;
                if (edgesUsed === n - 1) break;
            }
        }
        
        return uf.isConnected() ? weight : Infinity;
    }
    
    // Get original MST weight
    const originalWeight = getMSTWeight();
    
    const critical = [];
    const pseudoCritical = [];
    
    // Check each edge
    for (let i = 0; i < indexedEdges.length; i++) {
        const originalIndex = indexedEdges[i][3];
        
        // Check if edge is critical (excluding it increases MST weight)
        if (getMSTWeight(i) > originalWeight) {
            critical.push(originalIndex);
        }
        // Check if edge is pseudo-critical (including it keeps same MST weight)
        else if (getMSTWeight(-1, i) === originalWeight) {
            pseudoCritical.push(originalIndex);
        }
    }
    
    return [critical, pseudoCritical];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大小
时间复杂度O(E² log E)
空间复杂度O(E + V)
  • 时间复杂度：对每条边都要运行两次 Kruskal 算法，每次时间复杂度为 O(E log E)，共 E 条边
  • 空间复杂度：主要用于存储边的信息和并查集结构