最小生成树 Kruskal算法

还有一个Prim算法，以后补上

#include <iostream>
#include <algorithm>
#define debug(x) cout << #x << ": " << x << endl; 
const int maxn = 1000001;
int father[maxn];//father数组存放的是父亲结点

using namespace std;


struct Edge{
	int u; //左端点
	int v; //右端点
	int dis; //权值
}ed[maxn];


bool cmp(Edge a,Edge b){ // 结构体排序
	return a.dis < b.dis;
}
void init(int n){ // 初始化
	for(int i=1;i<=n;i++)
		father[i] = i;
}
int find_father(int x){ // 并查集核心操作
	if(x == father[x]) return x;
	int temp = find_father(father[x]);// 路径压缩
	return temp;
}
int Kruskal(int n,int m){
	int ans = 0; // 记入最小生成树的权值
	int num_Edge = 0;//边的数目
	for(int i = 0; i < m; i++){
		int fu = find_father(ed[i].u);//找最终父亲
		int fv = find_father(ed[i].v);//找最终父亲
		if(fu != fv){
			father[fu] = fv;//合并
			ans += ed[i].dis;
			num_Edge++;
			if(num_Edge == n-1) break;
		}
	}
	if (num_Edge != n-1) return -1;//退出条件
	else return ans;
}
int main(){
	int n, m;
	while (cin >> n >> m) {
		init(n);
		for (int i=0;i<m;i++) 
			cin >> ed[i].u >> ed[i].v>> ed[i].dis; //输入
		sort(ed, ed+m, cmp); //排序
		cout << Kruskal(n, m) << endl;
	}
	return 0;
}

参考自 CSDN：https://blog.csdn.net/qq_49786613/article/details/115309103