- 得到
V
，| E |的权重的中位数 边缘。 - 找出所有边的值不超过
V
，并获得子图- 如果子图已连接，
V
则是答案的上限，并减小V
，重复步骤1、2。 - 如果未连接子图，则 让连接的组件成为一个节点 ，并增加
V
，重复步骤1、2。
- 如果子图已连接，
然后，您可以在线性时间内解决问题。
PS：使用DFS判断子图已连接。复杂度为O（E / 2）+ O（E / 4）+ O（E / 8）+ … = O（E）
V，| E |的权重的中位数 边缘。
V，并获得子图
V则是答案的上限，并减小
V，重复步骤1、2。
V，重复步骤1、2。
然后，您可以在线性时间内解决问题。
PS：使用DFS判断子图已连接。复杂度为O（E / 2）+ O（E / 4）+ O（E / 8）+ … = O（E）
名师互学网 版权所有 (c)2021-2022 ICP备案号：晋ICP备2021003244-6号
