最小生成树（prim and kruskal）

最小生成树算法 

比较经典的是这两种 prim   kruskal

思想都是贪心的思想

然而我只会一种...kruskal

这里用到了并查集check关系

先将边权从小到大排序，每次选择没有选择的边中的最小边权，check一下是否会形成环，如果形成环就不选择 否则就选择这条边，就这么做下去...

用邻接表结构来记录边的两个顶点和边权

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=150005;
struct node{
    int u, v, cost;
}G[maxn];
int a[maxn];
void init(int N){
   for(int i=0; i<N; i++){
        a[i]=i;
   }
}
bool same(int x, int y){
    return a[x]==a[y];
}
int Find(int x){
    return a[x]==x?x:(a[x]=Find(a[x]));
}
void Merge(int x, int y){
    x=Find(x);
    y=Find(y);
    a[x]=y;
}
bool cmp(node a, node b){
    return a.cost<b.cost;
}

int main(){
    int n, m;
    cin>>n>>m;
    init(n);
    for(int i=0; i<m; i++){
        cin>>G[i].u>>G[i].v>>G[i].cost;
    }
    sort(G, G+m, cmp);
    ll ans=0;
    for(int i=0; i<m; i++){
        int U=G[i].u, V=G[i].v;
        U=Find(U), V=Find(V);
        if(!same(U, V)){
            Merge(U, V);
            ans+=G[i].cost;
        }
    }
    cout<<ans<<endl;
    return 0;
}