真正的Kruskal算法
```cpp
#include <bits/stdc++.h>
#define M 200100
using namespace std;
typedef long long ll;
struct node
{
int x;
int y;
int w;
}a[M];
int n,m,fa[M],p=1,ans;
bool cmp(node x,node y)
{
return x.w<y.w;
}
int find(int x)
{
if(x==fa[x])return x;
return fa[x]=find(fa[x]);
}
void Kruskal()
{
sort(a+1,a+m+1,cmp);
for(int i=1;i<=n;i++)fa[i]=i;
for(int i=1;i<=m;i++)
{
if(find(a[i].x)!=find(a[i].y))
{
ans+=a[i].w;
fa[find(a[i].x)]=a[i].y;
p++;
if(p==n)return;
}
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].w);
Kruskal();
printf("%d\n",ans);
return 0;
}
```
by Smile_Cindy @ 2018-07-25 23:28:13
@[石破天惊](/space/show?uid=9032) 你把数组开到200000再试试
by Smile_Cindy @ 2018-07-25 23:33:04
@[Alpha](/space/show?uid=87058) 还是数组开小了，谢谢dalao
by 石破天惊 @ 2018-07-25 23:35:22
$emm$
by Juanzhang @ 2018-07-25 23:35:25
@[Alpha](/space/show?uid=87058) %%%%
by ylxmf2020 @ 2018-07-26 07:27:51