数据结构-最小生成树 （C语言代码）

解题思路:
        留个笔记，普鲁斯卡尔算法（和本题数据不符）

注意事项:

参考代码:

#include <iostream>
using namespace std;
struct mp{
	int x;
	int y;
	int s;
}e[105];
int note[105];
bool check(int a,int b);
int root(int x);
bool cmp(mp a,mp b);
int main(){
	int n,m;
	cin>>n>>m;
	for(int i=0;i<m;i++){
		cin>>e[i].x>>e[i].y>>e[i].s; //输入数据 
	}
	for(int i=1;i<=n;i++)	//初始化 
		note[i]=i;
	sort(e,e+m,cmp);
	int sum=0,count=0;//排序 
	for(int i=0;i<m;i++){	 //m条边 
		if(check(e[i].x,e[i].y)){  //并查集判断是否连通 
				sum+=e[i].s;		//没有连通，权值加起来 
				count++;			//记录数量 
				cout<<e[i].s<<endl;
		}
		if(count==n-1)	//count为n-1说明 最小生成树已经构建 
			break;
	}
	cout<<sum<<endl; 
	return 0;
}
bool cmp(mp a,mp b){
	return a.s<b.s;
}
bool check(int a,int b){
	int fx=root(a);
	int fy=root(b);
	if(fx!=fy){
		note[fx]=fy;
		return 1;
	}
	return 0;
}
int root(int x){
	int r=x;
	while(note[r]!=r){
		r=note[r];
	}
	int j,i=x;
	while(i!=r){
		j=note[i];
		note[i]=r;
		i=j;
	}
	return r;
}