最小生成树Kruskal模板题

Laoj P1782

```cpp
#include<iostream>
#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;

long long n,m,fa[200005],tot=0;long long a[20005],ans=0;

long long getfa(int a){
if(fa[a]==a)return fa[a];
else{
fa[a]=getfa(fa[a]);
return fa[a];
}
}

struct road{
long long u,v;
long long w;
}r[500005];

int comp(road x,road y){
return x.w<y.w;
}

int main(){
scanf("%lld%lld",&n,&m);
for(long long i=1;i<=n;i++)fa[i]=i;
for(long long i=1;i<=m;i++)scanf("%lld%lld%lld",&r[i].u,&r[i].v,&r[i].w);
sort(r+1,r+m+1,comp);
for(long long i=1;i<=m;i++){
long long fu=getfa(r[i].u),fv=getfa(r[i].v);
if(fu!=fv){
fa[fv]=fu;
ans+=r[i].w;
tot++;
}
if(tot==n-1){
printf("%lld ",ans);
return 0;
}
}
if(tot<n-1||n==0||m==0)printf("0 ");
}
```
注意数据大，用long long.

注意倒数第二行的判断及输出0.