kruskal模板题-题解

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+9;
int f[N],n,m,ans,cnt;
struct node{
int x,y,z;
}a[N];
bool cmp(node n,node m){
return n.z<m.z;
}
int find(int x){
if(f[x]x){
return x;
}
return f[x]=find(f[x]);
}
void merge(int x,int y){
x=find(x);
y=find(y);
f[x]=y;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
f[i]=i;
}
for(int i=1;i<=m;i++){
cin>>a[i].x>>a[i].y>>a[i].z;
}
sort(a+1,a+m+1,cmp);
for(int i=1;i<=m;i++){
if(find(a[i].x)!=find(a[i].y)){
merge(a[i].x,a[i].y);
cnt++;
ans+=a[i].z;
}
}
if(cntn-1)cout<<ans;
else cout<<"orz";
return 0;
}