基本最小生成树—Kruskal

/* 对权值进行排序，然后从小到大进行判断， 如果加入这条边，不成环则是所求树的边。 （并查集） */
#include 
#include 
#include 
using namespace std;
int par[1020];
int ran[1020];
struct edge{
    int u,v,dis;
}e[1020];
bool cmp(edge a,edge b)// 以边由小到大排序 
{
    return a.disint find(int x)  //查找根节点 
{
    int r = x;
    while(par[r]!=r)
    {
        r = par[r];
    }
    int i = x,j;
    while(par[i]!=r)
    {
        j = par[i];
        par[i] = r;
        i = j;
    }
    return r;
}
void merge(int x,int y)  
{
    x = find(x);
    y = find(y);
    if(ran[x]else
    {
        par[y] = x;
        if(ran[x]==ran[y])
        ran[x]++;
    }
}

int main()
{
    int n;
    while(scanf("%d",&n),n)
    {
        int m;
        cin>>m;
        for(int i = 1;i<=n;i++)
        {
            par[i] = i;
            ran[i] = 0;
        }
        for(int i = 0;icin>>e[i].u>>e[i].v>>e[i].dis;
        }
        sort(e,e+m,cmp);
        int sum = 0;
        for(int i = 0;iif(find(e[i].u)!=find(e[i].v)) // 如果两点根节点不同，将他们合并并且加入生成图中 
            {
                sum+=e[i].dis;
                merge(e[i].u,e[i].v);
            }
        }
        cout<return 0;
}
/* 6 10 1 2 6 1 4 5 4 6 2 6 5 6 5 2 3 1 3 1 3 4 5 3 6 4 3 5 6 3 2 5 15 */