题解

并查集+kruskal

#include<iostream>
#include<algorithm>
using namespace std;
const int N=2e5+5;
struct node{
int x,y,z;
}s[N];
bool cmp(node a,node b){
    return a.z<b.z;
}
int f[N];//代表i的祖先
int find(int x){//找x的祖先 
	if(f[x]==x)return x;
	return f[x]=find(f[x]);//当前x的祖先
	//find(f[x])找x祖先的祖先 
} 
void unite(int x,int y){
	int rootx=find(x);//找x的祖先
	int rooty=find(y);//找y的祖先
	//如果x和y的祖先不同 就把y设为x祖先的祖先 
	if(rootx!=rooty)f[rootx]=rooty; 
}
int main(){
	int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)f[i]=i;
    for(int i=1;i<=m;i++)
        cin>>s[i].x>>s[i].y>>s[i].z;
    sort(s+1+m,cmp);//排序，优先选权值最小
    int ans=0,cnt=0;
    for(int i=1;i<=m;i++){
        if(find(s[i].x)==find(s[i].y))continue;//如果已经联通（有同一个祖先），那么跳过
        unite(s[i].x,s[i].y);//否则的话链接两个点
        cnt++;//记录边的个数
        ans+=s[i].z;
    }
    if(cnt==n-1)cout<<ans;//当有n-1条边时，说明全部联通
    else cout<<"orz";
	return 0;
}