PTA 最小生成树-kruskal_pta6-2最小生成数

7-92 最小生成树-kruskal
分数 10

全屏浏览题目
作者 任唯
单位 河北农业大学
题目给出一个无向连通图，要求求出其最小生成树的权值。

温馨提示：本题请使用kruskal最小生成树算法。

输入格式:

输出格式:

输出一个整数表示最小生成树的各边的长度之和。

输入样例:
4 5
1 2 2
1 3 2
1 4 3
2 3 4
3 4 3
输出样例:
7
代码长度限制
16 KB
时间限制
500 ms
内存限制
64 MB

代码分享及思路分享：

 
#include <iostream>
#include<bits/stdc++.h>
#include <algorithm>
using namespace std;
struct edge{
    int u,v;
    int value;
}s[1000001];
int f[1000001];//用f数组的下标和对应存储的值来判断是否已经连通
int find(int x){
    if(x!=f[x])  return f[x]=find(f[x]);
    return f[x];
}//调用递归
bool cmp(edge a,edge b){
    return a.value<b.value;
}//以边从小到大排序
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++){
     scanf("%d%d%d", &s[i].u, &s[i].v, &s[i].value);//这里要用scanf如果用cin会报运行超时
    }//数据的输入
    int num=0,sum=0;
    sort(s+1,s+m+1,cmp);//对边进行排序
    for(int i=1;i<=n;i++){
        f[i]=i;
    }
    for(int i=0;i<=m;i++){
        int fu=find(s[i].u);
        int fv=find(s[i].v);
        if(fu!=fv){
            f[fu]=fv;
            sum+=s[i].value;
            num++;
            if(num==n-1)//边数为顶点数-1，所有最小边都已经找到就可以退出了
                break;
        }
    }
    cout<<sum;
    return 0;
}