kruskal算法

/*kruskal算法思想：每次选择图中最小边权的边，如果边两端的顶点在不同的连通块中，就把这条边加入最小生成树中。kruskal伪代码如下：int kruskal(){	令最小生成树的边权之和为ans、最小生成树的当前边数Num_Edge;	将所有边按边权从小到大排序；	for(从小到大枚举所有边)	{		if(当前测试边的两个端点在不同的连通块中)		{			将该测试边加入最小生成树中；			ans+=测试边的边权；			最小生成树的当前边数Num_Edge加1；			当边数Num_Edge等于顶点数减1时结束循环；		}	}	return ans;}*///kruskal算法应用实现代码#include<cstdio>#include<algorithm>using namespace std;const int MAXV = 110;const int MAXE = 10010;//边集定义部分struct edge{	int u, v;//边的两个端点编号	int cost;//边权}E[MAXE];//最多有MAXE边bool cmp(edge a, edge b){	return a.cost < b.cost;}//并查集部分int father[MAXV];//并查集数组/*int findFather(int x)//并查集查询函数{	int a = x;	while (x != father[x])	{		x = father[x];	}	//路径压缩	while (a != father[a])	{		int z = a;		a = father[a];		father[z] = x;	}	return x;}*/int findFather(int x)//递归版{	if (x == father[x])		return x;	else	{		int f = findFather(father[x]);		father[x] = f;		return f;	}}//kruskal部分，返回最小生成树的边权之和，参数n为顶点个数，m为图的边数int kruskal(int n, int m){	//ans为所求边权之和，Num_Edge为当前生成树的边数	int ans = 0, Num_Edge = 0;	for (int i = 0; i < n; i++)//顶点范围是[0,n-1]	{		father[i] = i;//并查集初始化	}	sort(E, E + m, cmp);//所有边按边权从小到大排序	for (int i = 0; i < m; i++)//枚举所有边	{		int faU = findFather(E[i].u);//查询测试边两个端点所在集合的根结点		int faV = findFather(E[i].v);		if (faU != faV)//如果不在一个集合中		{			father[faU] = faV;//合并集合(即把测试边加入最小生成树中)			ans += E[i].cost;//边权之和增加测试边的边权			Num_Edge++;//当前生成树的边数加1			if (Num_Edge == n - 1)break;//边数等于顶点数减1时结束算法		}	}	if (Num_Edge != n - 1)return -1;//无法连通时返回-1	else return ans;//返回最小生成树的边权之和}int main(){	int n, m;	scanf("%d%d", &n, &m);//顶点数，边数	for (int i = 0; i < m; i++)	{		scanf("%d%d%d", &E[i].u, &E[i].v, &E[i].cost);//两个端点的编号、边权	}	int ans = kruskal(n, m);//kruskal算法入口	PRintf("%d/n", ans);	return 0;}