【模板】最小生成树优化版（Kruskal）

最小生成树问题
给定一个无向图，如果它的某个子图中任意两个顶点都互相连通，那么这个图就叫做生成树。如果边上有权值，那么使得边权和最小的生成树叫做最小生成树（MST）。

但是！！！
如果这个图不连通呢？
有时题目会让你自行判断图是否连通，若不连通输出-1，连通输出权值和。
其实我们只需要加入一个flag判断一下就好了

下面是我用kruskal写的最小生成树模板并加入了判断，如果不了解kruskal的原理，请点击(https://blog.csdn.net/weixin_43820631/article/details/89741002)

#include<bits/stdc++.h>
using namespace std;
#define maxn 300005
#define ll long long

int n,m,t,path,flag;
int f[maxn];
struct edge{
    int s,t,val;
}a[maxn];

bool cmp(edge x,edge y){
    return x.val<y.val;
}

int find(int x){
    if(f[x]==x)return x;
    else return f[x]=find(f[x]);
}

void kruskal(){
    for(int i=0;i<m;i++){
        int u=find(a[i].s);
        int v=find(a[i].t);
        if(u==v)continue;
        t+=a[i].val;
        f[u]=v;
        path++;
        if(path==n-1){
            flag=1;
            break;
        }
    }
}

int main()
{
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)
        f[i]=i;
    for(int i=0;i<m;i++)
        scanf("%d %d %d",&a[i].s,&a[i].t,&a[i].val);
    sort(a,a+m,cmp);
    kruskal();
    if(flag==1)printf("%d",t);
    else printf("-1");
    return 0;
}