What is the main pattern used to solve the Minimize Maximum Component Cost problem?

The main pattern used is binary search over the possible maximum edge weights, combined with Union-Find to manage connected components in the graph.

How does sorting the edges help in this problem?

Sorting the edges allows binary search to efficiently explore the valid range of edge weights, ensuring that the solution is both correct and optimal.

Can this approach be applied to graphs with negative edge weights?

No, this approach assumes positive edge weights. Modifications would be required to handle negative weights effectively.

Why is Union-Find important in this problem?

Union-Find is crucial for efficiently tracking connected components and ensuring that the graph can be split into at most k components while minimizing the maximum edge weight.

How does GhostInterview assist in solving graph problems like Minimize Maximum Component Cost?

GhostInterview helps by providing structured guidance on applying binary search, optimizing graph connectivity, and using Union-Find to solve such problems efficiently.

#3613

Medium

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

最小化连通分量的最大成本

给你一个无向连通图，包含 n 个节点，节点编号从 0 到 n - 1 ，以及一个二维整数数组 edges ，其中 edges[i] = [u i , v i , w i ] 表示一条连接节点 u i 和节点 v i 的无向边，边权为 w i ，另有一个整数 k 。你可以从图中移除任意数量的边，使得…

二分查找排序并查集图

题目描述

给你一个无向连通图，包含 n 个节点，节点编号从 0 到 n - 1，以及一个二维整数数组 edges，其中 edges[i] = [u_i, v_i, w_i] 表示一条连接节点 u_i 和节点 v_i 的无向边，边权为 w_i，另有一个整数 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⁴
0 <= edges.length <= 10⁵
edges[i].length == 3
0 <= u_i, v_i < n
1 <= w_i <= 10⁶
1 <= k <= n
输入图是连通图。

lightbulb

解题思路

方法一：排序 + 并查集

如果 $k = n$ ，说明所有的边都可以被移除，此时所有的连通分量都是孤立的节点，最大成本为 0。

否则，我们可以将所有的边按权值从小到大排序，然后使用并查集来维护连通分量。

我们不妨假设初始时所有节点并不联通，初始时每个节点都是一个独立的连通分量。我们从权值最小的边开始，尝试将其加入到当前的连通分量中。如果加入后连通分量的数量已经小于等于 $k$ ，则说明剩余的边都可以被移除，此时当前边的权值就是我们要找的最大成本，返回该权值即可。否则，我们继续处理下一条边。

时间复杂度 $O(n \times \log n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 是节点的数量。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

class Solution:
    def minCost(self, n: int, edges: List[List[int]], k: int) -> int:
        def find(x: int) -> int:
            if p[x] != x:
                p[x] = find(p[x])
            return p[x]

        if k == n:
            return 0
        edges.sort(key=lambda x: x[2])
        cnt = n
        p = list(range(n))
        for u, v, w in edges:
            pu, pv = find(u), find(v)
            if pu != pv:
                p[pu] = pv
                cnt -= 1
                if cnt <= k:
                    return w
        return 0

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
The candidate efficiently handles the graph's connectivity with Union-Find.
question_mark
The candidate demonstrates understanding of binary search applied to optimization problems.
question_mark
The candidate uses edge sorting as a natural step to streamline the solution process.

warning

常见陷阱

外企场景

error
Overlooking the need to sort the edges before applying binary search.
error
Misunderstanding the edge weights when performing Union-Find operations.
error
Failing to handle the k-component constraint correctly, leading to an incorrect solution.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Increase the number of components allowed (k) and observe how it affects the optimization process.
arrow_right_alt
Change the graph from being connected to having multiple disjoint subgraphs and analyze the approach.
arrow_right_alt
Allow negative edge weights and evaluate how the algorithm adapts to this new scenario.

help

常见问题

外企场景

继续练习

#3608 包含 K 个连通分量需要的最小时间 #3600 升级后最大生成树稳定性 #3532 针对图的路径存在性查询 I