证明及实现
感性的理解一下，我们最终要选择 n - 1 条边加入集合，那么肯定要选择边权尽可能少的。
在第 3 步时，如果我们不选目前这条边，为了使两个连通块连通，一定会更劣，所以选择这条边就是最优的。
实现的话，我们需要排序，为了维护连通块，还需要并查集。
时间复杂度 O(M log M)
性的理解一下，我们最终要选择 n - 1 条边加入集合
发布时间 2023-10-09 20:59:05作者: yzxznb
证明及实现
感性的理解一下，我们最终要选择 n - 1 条边加入集合，那么肯定要选择边权尽可能少的。
在第 3 步时，如果我们不选目前这条边，为了使两个连通块连通，一定会更劣，所以选择这条边就是最优的。
实现的话，我们需要排序，为了维护连通块，还需要并查集。
时间复杂度 O(M log M)