kruskal求最小生成树

思路：先按照每条边的权值排序，从小到大枚举每条边，如果这条边两个顶点的祖宗节点不一样，连接上这条边并且计数器加一，最后如果计数器小于顶点个数-1的话，就说明不到n个点，就不可能，否则输出答案
代码如下：

#include<iostream>
using namespace std;
const	int N=100010;
int p[N];
int find(int x)
{
   if(x!=p[x])
p[x]=find(p[x]);
return p[x];
}
int main()
{
   
	int n;int m;
	while(scanf("%d",&n)!=EOF&&n)
	{
   
		int cnt=0;
		scanf("%d",&m);
		for(int i=1;i<=n;i++)
		p[i]=i;
		while(m--)
		{
   int a,b;
		cin>>a>>b;
		p[find(a)]=find(b);
		}
		for(int i=1;i<=n;i++)
		{
   
			if(p[i]==i)
			cnt++;
		}
		cout<<cnt-1<<endl;
	}
 }