最小生成树的题目，并查集应用最完美的地方：最小生成树的 kruskal 算法
呵呵，第一次用并查集，具有纪念价值，所以附上代码，并有详细的注释。最短时间把它给攻下！！！
#include<iostream>
#include<algorithm>
using namespace std;
struct node //存储边信息的结点
{
int a,b; //一条边的两个点
int value;//边权值
}edge[15005];
node record[15005];//用来记录
int father[1005];//父结点
int rank[1005]; //秩
bool cmp(node a,node b)
{
return a.value<b.value;
}
void Make_Set(int n)//初始化一个集合
{
for(int i=0;i<=n;i++)
{
father[i]=i;
rank[i]=1;
}
}
int Find_Set(int x)//查找一个元素所在集合
{
if(x!=father[x])
{
father[x]=Find_Set(father[x]);//递归查找
}
return father[x];
}
bool Union(int a,int b)
{
int x=Find_Set(a);
int y=Find_Set(b);
if(x==y)return false;
// 合并将元素少的合并到元素多的集合中,使的树的高度相对较小
if(rank[x]>=rank[y])
{
father[y]=x;
rank[x]+=rank[y];
}
else
{
father[x]=y;
rank[y]+=rank[x];
}
return true;
}
int main()
{
int i,j=1,n,m,max=0,num=0;
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++)
scanf("%d%d%d",&edge[i].a,&edge[i].b,&edge[i].value);
Make_Set(n);
sort(edge+1,edge+m+1,cmp);
for(i=1;i<=m;i++)
{
if(Union(edge[i].a,edge[i].b))
{
num++;
if(edge[i].value>max)
max=edge[i].value;
record[j].a=edge[i].a;
record[j].b=edge[i].b;
j++;
}
if(num==n-1)break;
}
printf("%d/n%d/n",max,n-1);
for(i=1;i<n;i++)
printf("%d %d/n",record[i].a,record[i].b);
system("pause");
return 0;
}