3613. 最小化最大组件成本

Medium

题目描述

给定一个有 n 个节点的无向连通图，节点标号为 0 到 n-1，以及一个二维整数数组 edges，其中 edges[i] = [ui, vi, wi] 表示节点 ui 和 vi 之间有一条权重为 wi 的无向边，还给定一个整数 k。

你可以从图中删除任意数量的边，使得结果图最多有 k 个连通分量。

一个连通分量的成本定义为该分量中的最大边权重。如果一个分量没有边，则其成本为 0。

返回删除边后所有分量中最大成本的最小可能值。

示例 1：

输入：n = 5, edges = [[0,1,4],[1,2,3],[1,3,2],[3,4,6]], k = 2
输出：4
解释：
删除节点 3 和 4 之间的边（权重 6）。
得到的分量成本为 0 和 4，所以总体最大成本为 4。

示例 2：

输入：n = 4, edges = [[0,1,5],[1,2,5],[2,3,5]], k = 1
输出：5
解释：
不能删除任何边，因为只允许一个分量（k = 1）需要图保持完全连通。
单个分量的成本等于其最大边权重，即 5。

约束条件：

1 <= n <= 5 * 10^4
0 <= edges.length <= 10^5
edges[i].length == 3
0 <= ui, vi < n
1 <= wi <= 10^6
1 <= k <= n
输入图是连通的

解题思路

这是一个结合二分搜索和并查集的经典问题。核心思想是二分答案：

解题思路：

二分搜索框架：对最大成本进行二分搜索。左边界为0，右边界为所有边权重的最大值。
可行性检查：对于每个候选答案mid，我们需要判断是否能通过删除一些边，使得：
- 图最多有k个连通分量
- 每个分量的最大边权重不超过mid
并查集实现：只保留权重不超过mid的边，用并查集统计连通分量数量。如果分量数量不超过k，说明当前mid是可行的。
优化策略：
- 首先按边权重排序
- 在二分搜索中，只考虑权重不超过mid的边
- 使用并查集高效统计连通分量

算法流程：

提取所有边权重并排序去重，作为二分搜索的候选值
二分搜索最小的可行答案
对每个候选值，构建只包含不超过该权重的边的图，统计连通分量数量

这种方法的关键洞察是：如果某个权重W可行，那么所有大于W的权重也都可行，具有单调性。

代码实现

class Solution {
public:
    int minCost(int n, vector<vector<int>>& edges, int k) {
        // 提取并排序所有不同的权重
        set<int> weightSet;
        for (auto& edge : edges) {
            weightSet.insert(edge[2]);
        }
        vector<int> weights(weightSet.begin(), weightSet.end());
        weights.insert(weights.begin(), 0); // 添加0作为最小值
        
        // 二分搜索
        int left = 0, right = weights.size() - 1;
        int result = weights[right];
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int maxWeight = weights[mid];
            
            if (canAchieve(n, edges, k, maxWeight)) {
                result = maxWeight;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        
        return result;
    }
    
private:
    bool canAchieve(int n, vector<vector<int>>& edges, int k, int maxWeight) {
        // 并查集
        vector<int> parent(n);
        iota(parent.begin(), parent.end(), 0);
        
        function<int(int)> find = [&](int x) {
            return parent[x] == x ? x : parent[x] = find(parent[x]);
        };
        
        // 只连接权重不超过maxWeight的边
        for (auto& edge : edges) {
            if (edge[2] <= maxWeight) {
                int u = find(edge[0]);
                int v = find(edge[1]);
                if (u != v) {
                    parent[u] = v;
                }
            }
        }
        
        // 统计连通分量数量
        set<int> components;
        for (int i = 0; i < n; i++) {
            components.insert(find(i));
        }
        
        return components.size() <= k;
    }
};

class Solution:
    def minCost(self, n: int, edges: List[List[int]], k: int) -> int:
        # 提取并排序所有不同的权重
        weights = sorted(set(edge[2] for edge in edges))
        weights = [0] + weights  # 添加0作为最小值
        
        # 二分搜索
        left, right = 0, len(weights) - 1
        result = weights[right]
        
        while left <= right:
            mid = (left + right) // 2
            max_weight = weights[mid]
            
            if self.can_achieve(n, edges, k, max_weight):
                result = max_weight
                right = mid - 1
            else:
                left = mid + 1
        
        return result
    
    def can_achieve(self, n: int, edges: List[List[int]], k: int, max_weight: int) -> bool:
        # 并查集
        parent = list(range(n))
        
        def find(x):
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]
        
        # 只连接权重不超过max_weight的边
        for u, v, w in edges:
            if w <= max_weight:
                root_u, root_v = find(u), find(v)
                if root_u != root_v:
                    parent[root_u] = root_v
        
        # 统计连通分量数量
        components = len(set(find(i) for i in range(n)))
        
        return components <= k

public class Solution {
    public int MinCost(int n, int[][] edges, int k) {
        // 提取并排序所有不同的权重
        var weightSet = new HashSet<int>();
        foreach (var edge in edges) {
            weightSet.Add(edge[2]);
        }
        var weights = weightSet.OrderBy(x => x).ToList();
        weights.Insert(0, 0); // 添加0作为最小值
        
        // 二分搜索
        int left = 0, right = weights.Count - 1;
        int result = weights[right];
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int maxWeight = weights[mid];
            
            if (CanAchieve(n, edges, k, maxWeight)) {
                result = maxWeight;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        
        return result;
    }
    
    private bool CanAchieve(int n, int[][] edges, int k, int maxWeight) {
        // 并查集
        int[] parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
        
        int Find(int x) {
            if (parent[x] != x) {
                parent[x] = Find(parent[x]);
            }
            return parent[x];
        }
        
        // 只连接权重不超过maxWeight的边
        foreach (var edge in edges) {
            if (edge[2] <= maxWeight) {
                int rootU = Find(edge[0]);
                int rootV = Find(edge[1]);
                if (rootU != rootV) {
                    parent[rootU] = rootV;
                }
            }
        }
        
        // 统计连通分量数量
        var components = new HashSet<int>();
        for (int i = 0; i < n; i++) {
            components.Add(Find(i));
        }
        
        return components.Count <= k;
    }
}

var minCost = function(n, edges, k) {
    // 提取并排序所有不同的权重
    const weightSet = new Set();
    for (const edge of edges) {
        weightSet.add(edge[2]);
    }
    const weights = [0, ...Array.from(weightSet).sort((a, b) => a - b)];
    
    // 二分搜索
    let left = 0, right = weights.length - 1;
    let result = weights[right];
    
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        const maxWeight = weights[mid];
        
        if (canAchieve(n, edges, k, maxWeight)) {
            result = maxWeight;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    
    return result;
};

function canAchieve(n, edges, k, maxWeight) {
    // 并查集
    const parent = Array.from({length: n}, (_, i) => i);
    
    function find(x) {
        if (parent[x] !== x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    
    // 只连接权重不超过maxWeight的边
    for (const [u, v, w] of edges) {
        if (w <= maxWeight) {
            const rootU = find(u);
            const rootV = find(v);
            if (rootU !== rootV) {
                parent[rootU] = rootV;
            }
        }
    }
    
    // 统计连通分量数量
    const components = new Set();
    for (let i = 0; i < n; i++) {
        components.add(find(i));
    }
    
    return components.size <= k;
}

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型	值
时间复杂度	O(E log W · (E + N))
空间复杂度	O(N + W)

其中：

E 是边的数量
N 是节点数量
W 是不同权重值的数量
二分搜索需要 O(log W) 次
每次检查需要 O(E + N) 时间进行并查集操作

题目描述#

解题思路#

代码实现#

复杂度分析#

题目描述

解题思路

代码实现

复杂度分析