déce.18 最小生成树板题

https://www.luogu.com.cn/problem/P3366

搞半天ACM不考树剖
白练那么久

最小生成树：
取\(n-1\)条边使图联通
边权排序，并查集判断能否取这条边

回忆了以下并查集的用法

#include<bits/stdc++.h>
using namespace std;
#define in Read()
typedef long long ll;

int in{
    int i=0,f=1; char ch=0;
    while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
    if(ch=='-') f=-1, ch=getchar();
    while('0'<=ch&&ch<='9') i=(i<<1)+(i<<3)+ch-48, ch=getchar();
    return i*f;
}

const int N=2e5+5;
int n,m;
struct edge{
    int u,v,w;
}e[N<<1];
int fa[N],tot,cnt,ans;

int get(int x){ return x==fa[x]?x:fa[x]=get(fa[x]);}

void Add(int u,int v,int w){
    ++tot;
    e[tot].u=u;
    e[tot].v=v;
    e[tot].w=w;
}

bool cmp(const edge &a, const edge &b){return a.w<b.w;}

int main(){

    // freopen("1.in","r",stdin);

    n=in,m=in;
    for(int i=1;i<=m;++i){
        int u=in,v=in,w=in;
        Add(u,v,w);
    }

    sort(e+1,e+m+1,cmp);
    for(int i=1;i<=n;++i) fa[i]=i;

    for(int i=1;i<=tot;++i){
        int u=get(e[i].u), v=get(e[i].v);
        if(u==v) continue;
        ++cnt;
        ans+=e[i].w;
        fa[u]=v;
        if(cnt==n-1) break;
    }

    if(cnt<n-1) printf("orz");
    else printf("%d\n",ans);
    return 0;
    
}