最小生成樹模板

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct Tree{

    int s,e,w;

    bool operator<(Tree a)const{

        return a.w>w;

    }

};

int p[100000];

int Find(int a){

    return p[a]==a ? a:p[a] = Find(p[a]);

}

ll Kruskal(int n,int m) {

    Tree dot[m];

    for(int i=0;i<n;i++) p[i]=i;

    for (int i=0;i<m;i++)

        cin >>dot[i].s>>dot[i].e>>dot[i].w;

    sort(dot,dot+m);

    ll ans=0,cnt = 0;

    for (int i=0,x,y;i<m;i++) {

        x = Find(dot[i].e);

        y = Find(dot[i].s);

        if(x==y) continue;

        else {

            p[y] = x;

            ans +=dot[i].w;

        }

    }

    return ans;

}