Kruskal模板

Kruskal模板

struct Edge

{

    int from,to,v;

}edge[maxn*10];

int fa[maxn];

int n,m;

int find(int x)

{

    return fa[x] == x ? x : fa[x] = find(fa[x]);

}

bool cmp(Edge a, Edge b)

{

    return a.v <b.v;

}

ll kruskal()

{

    for(int i = 1; i <= n; i++) fa[i] = i;

    sort(edge+1,edge+m+1,cmp);

    ll ans = 0;

    int cnt = 0;

    for(int i = 1; i <= m; i++){

        int x = find(edge[i].from);

        int y = find(edge[i].to);

        if(x != y){

            fa[x] = y;

            ans += (ll)edge[i].v;

            if(++cnt == n-1) break;

        }

    }

    return ans;

}