每次都找最小的边,一直到n-1个边为止,是关于边的算法,时间复杂度为mlog(m)
using namespace std;
const int N=5e5+10;
struct edge{
int u,v,w;
}edge[N];
int fa[N];
int ans=0;
int cnt=0;
int n,m;
bool cmp(struct edge a,struct edge b){
return a.w<b.w;
}
int f(int x){
return fa[x]==x?x:f(fa[x]);
}
void Kruskal(){
for(int i=1;i<=n;i++){
fa[i]=i;
}
sort(edge+1,edge+1+m,cmp);
for(int i=1;i<=m;i++){
if(cnt==n-1)break;
int u=edge[i].u;
int v=edge[i].v;
int a=f(u);
int b=f(v);
if(a==b)continue;
else{
ans+=edge[i].w;
cnt++;
fa[b]=a;
}
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>edge[i].u>>edge[i].v>>edge[i].w;
}
Kruskal();
cout<<ans;
return 0;
}