#include <iostream.h>        #define Max 100                typedef struct{                 int u;                 int v;                 int weight;        }edge;        edge edges[Max];        int nodes[Max];        void interchange(edge* m,edge* n)        {            edge temp=*m;            *m=*n;            *n=temp;                }        int partition(edge array[],int p,int q)        {            int i,j;            i=p;            j=q+1;            while(1)            {                do i++;                while((array[i].weight<array[p].weight)&&(i!=q));                do j--;                while((array[j].weight>array[p].weight)&&(j!=p));                if(i<j)                    interchange(&array[i],&array[j]);                else                    break;            }            interchange(&array[p],&array[j]);            return j;                }        void quicksort(edge array[],int p,int q)        {            int j;            if (p<q)            {                j=partition(array,p,q);                quicksort(array,p,j-1);                quicksort(array,j+1,q);            }        }        void main()        {                int i,j,m, n, nodenum, edgenum,safe,cost=0,flag=1 ;                int presult = 0;                        cout<<"Input the number of nodes and edges:";                cin>>nodenum>>edgenum;                cout<<"请输入每条边的起点、终点及权值："<<endl;                for(i = 0; i < edgenum; i++)                {                     cin>>edges[i].u>>edges[i].v>>edges[i].weight;                                     }                for(i=1;i<=nodenum;i++)                    nodes[i]=0;                quicksort(edges,0,edgenum-1);                for(i = 0; i < edgenum ; i++)                {                                       m = edges[i].u;                        n = edges[i].v;                        safe = 0;                        if(nodes[m] == 0 &&nodes[n] == 0){                                nodes[m] = flag;                                 nodes[n] =flag;                                 flag++;                                safe = 1;//a safe edge                                }                        else                        {                            if(nodes[m] == 0 ||nodes[n] == 0 )                            {                                if(nodes[m] == 0 )                                                            nodes[m] = nodes[n];                                else nodes[n]=nodes[m];                                                                safe = 1;//a safe edge                            }                            else                                 if(nodes[m] != nodes[n])                                {                                                         for(j = 1; j <= nodenum; j++)                                      {                                        if((nodes[j] == nodes[m] || nodes[j] == nodes[n])&&(j!=m&&j!=n))                                        {                                                nodes[j] = flag;                                        }                                      }                                        nodes[m]=flag;                                      nodes[n]=flag;                                      flag++;                                                                safe = 1;//a safe edge                                        }                                }                                                 if(safe == 1){//reserve a safe edge                                        edges[presult].u = m;                                edges[presult].v = n;                                edges[presult].weight = edges[i].weight;                                presult++;                        }                                     if(presult == nodenum-1 ){//found mst                                        break;                        }                 }                cout<<"Print the result:"<<endl;                cout<<"起点   终点   权值"<<endl;                        for(i = 0; i < presult; i++)                        {                            cost=cost+edges[i].weight;                            cout<<edges[i].u<<"       "<< edges[i].v<<"         "<< edges[i].weight<<endl;                        }                        cout<<"最小生成树的权值为："<<cost<<endl;                               }