纯粹的最小生成树算法

#include<iostream>
#include<algorithm> 
using namespace std;
const int N=110,M=1e6+10;
int p[N],n;
int find(int x)
{
   if(x!=p[x]) p[x]=find(p[x]);
   return p[x];
}
struct Edge
{
	int a,b,w;
}q[M];
bool cmp(Edge a,Edge b)
{
	return a.w<b.w;
}
int main()
{
	int m;
	cin>>n;
	while(n)
	{
		int cost=0;
		for(int i=1;i<=n;i++) p[i]=i;
		m=(n-1)*n/2;
		for(int i=0;i<m;i++)
		{
		    int a,b,w;
		    cin>>a>>b>>w;
		    q[i].a=a,q[i].b=b,q[i].w=w;
		}
		sort(q,q+m,cmp);
		for(int i=0;i<m;i++)
		{
			int a=find(q[i].a),b=find(q[i].b);
			if(a!=b)
			{
				p[a]=b;
				cost+=q[i].w;
			}
		}
		cout<<cost<<endl;
		cin>>n; 
	}          
	return 0;
}

解题思路:

注意事项:

参考代码: