最小生成树

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

const int MAXN=5000+10;
const int MAXM=(int)2e5+10;

int pre[MAXN];
struct Edge{
  int u,v,w;
  bool operator<(const Edge &t){
    return w<t.w;
  }
} e[MAXM];
ll ans;

int find(int x);
void merge(int x,int y);
bool Kruskal(int n,int m);

int main()
{
  int n,m;
  cin>>n>>m;
  for (int i=0;i<m;i++) {
    scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
  }
  for (int i=1;i<=n;i++) {
    pre[i]=i;
  }
  if (Kruskal(n,m)) {
    cout<<ans<<endl;
  } else {
    puts("orz");
  }
  return 0;
}

int find(int x)
{
  return x==pre[x] ? x : pre[x]=find(pre[x]);
}

void merge(int x,int y)
{
  pre[find(x)]=find(y);
}

bool Kruskal(int n,int m)
{
  sort(e,e+m);
  ans=0;
  int cnt=0;
  for (int i=0;i<m;i++) {
    int x=find(e[i].u),y=find(e[i].v);
    if (x!=y) {
      merge(x,y);
      ans+=e[i].w;
      if (++cnt==n-1) {
        return true;
      }
    }
  }
  return false;
}