最小生成树模板

这是一篇讲kruskal的题解

看题解很多大佬只讲kruskal思路，我就来写写整个代码的思路

思路：

核心思想不是堆，不是查找，而是sort

我们可以这么想：因为是最小的路径，所以我们可以排序一下，把节点根据长度从小到达大排序一下

所以，我们先开个结构体来储存节点和边长（开结构体是为了方便sort排序）

struct node{
	int p1,p2,val;//p1是出发点，p2是目的地，val是路的长度
};

因为是根据节点排序，所以我们可以开个cmp函数

int cmp(node &A,node &B){//不写取地址符也可以
	return A.val<B.val;//保持路径小的在前面
}

那么问题来了：怎么不走重复的点呢？

这需要我们的并查集。这里我不多讲并查集了，不会的大佬可以参考这个

那么我们就可以写一个find函数，用来合并两个已经走过的点

int find(int k){
	if(f[k]==k)return k;
	return f[k]=find(f[k]);//路径压缩
}

然后再sort排序，整个代码就成型了

#include<cstdio>
#include<algorithm>
using namespace std;
int f[5001];
int find(int k){
	if(f[k]==k)return k;
	return f[k]=find(f[k]);
}
struct node{
	int p1,p2,val;
};
int cmp(node &A,node &B){
	return A.val<B.val;
}
node qwq[200001];
int ans,cnt;//cnt是用来判断能不能联通
int n,m;
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&qwq[i].p1,&qwq[i].p2,&qwq[i].val);
	}
	for(int i=1;i<=5000;i++)f[i]=i;//初始化
	sort(qwq+1,qwq+m+1,cmp);//sort排序
	for(int i=1;i<=m;i++){
		if(find(qwq[i].p1)!=find(qwq[i].p2)){
			cnt++;
			f[find(qwq[i].p1)]=find(qwq[i].p2);//合并
			ans+=qwq[i].val;
		}
		if(cnt==n-1){
			printf("%d",ans);
			return 0;
		}
	}
	printf("orz\n");//不能联通就输出orz,但是好像测试点中没有不联通的数据
	return 0;
}