AcWing 859. Kruskal算法求最小生成树
原题链接
简单
作者:
Eavan
,
2021-08-20 11:27:23
,
所有人可见
,
阅读 346
Kruskal算法
时间复杂度:$O(mlogm)$
思路:
- 将所有边按权重从小到大排序(快排)
- 枚举每条边a, b 权重c
若ab不连通,将这条边也加入集合中
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N = 200010;
int n, m;
int p[N]; // 并查集
struct Edge
{
int a, b, w;
// 按权重来排序
bool operator< (const Edge &W) const
{
return w < W.w;
}
}edges[N];
int find(int x) // 返回x的祖宗节点 + 路径压缩
{
if(p[x] != x) p[x] = find(p[x]); // 若x不是根节点,那就让x等于它的祖宗节点
return p[x];
}
// kruskal算法
int kruskal()
{
sort(edges, edges + m); // 对应第一步: 将所有边按权重从小到大排序
for(int i = 1; i <= n; i++) p[i] = i; // 初始化并查集
// 从小到大枚举所有边
int res = 0, cnt = 0;
// res 存的是最小生成树所有树边的权重适合
// cnt 存的是最小生成树的边的个数
for(int i = 0; i < m; i++)
{
int a = edges[i].a;
int b = edges[i].b;
int w = edges[i].w;
a = find(a), b = find(b);
if(a != b)
{
p[a] = b;
res += w;
cnt++;
}
}
if(cnt < n - 1) cout << "impossible" << endl;
else cout << res << endl;
}
int main()
{
cin >> n >> m;
for(int i = 0; i < m; i++)
{
int a, b, w;
cin >> a >> b >> w;
edges[i] = {a, b, w};
}
kruskal();
return 0;