prim和kruskal（最小生成树）（kruskal模板）

题目： P3366 【模板】最小生成树

n为点，m为边

prim:
    O(nlgn)    //以边遍历点，因其一边有两个点，所以每个点会有两次判断，所以复杂度为n^2，通过堆优化可以变成 nlgn
    prim是从一个点散出去找与其相连的未被访问的最小边
    所以要用前向星的add
kruskal:
    O(mlgm)    //复杂度主要是为边排序  //n小就用prim  //m小就用kruskal
    kruskal是从全局找未被访问的最小边
    所以只要边排序就够了，用不到add

前向星：没有add函数的node不是前向星
       通过前向星可以访问到与i相连点和边

以下是kruskal

#include<bits/stdc++.h>
using namespace std;
int const N=5e3+7;
int const M=2e5+7;
int n,m;
struct node{
    int a,next,len;
}e[M];
bool cmp(node a,node b){
    return a.len < b.len ;
}
int f[N];
int find(int x){
    return f[x]==x?x:f[x]=find(f[x]);
}
void merge(int x,int y){
    f[find(x)]=find(y);
}
void kruskal(){
    int cnt=0,sum=0,flag=0;
    sort(e+1,e+m+1,cmp);
    for(int i=1;i<=n;++i) f[i]=i;
    for(int i=1;i<=m;++i){
        int a=e[i].a , b=e[i].next ;
        if(find(a)!=find(b)){
            merge(a,b);
            cnt++;
            sum+=e[i].len ;
            if(cnt>=n-1) {
                flag=1;break;
            }
        }
    }
    if(flag) cout << sum;
    else cout << "orz";
}
int main(){
    cin >> n >> m;
    for(int i=1;i<=m;++i){
        cin >> e[i].a >> e[i].next >> e[i].len ;
    }
    kruskal();       //克鲁斯卡尔 
    return 0;
}