最小生成樹Kruskal算法+并查集檢查連通

/*
10 6
1 2 6
1 3 1
1 4 5
2 3 5
2 5 3
3 4 5
3 5 6
3 6 4
4 6 2
5 6 6
*/

// 本例解決最小生成樹問題
// 并查集來加快效率
// cruscal算法針對稀疏矩陣

#include<stdio.h>
#include<string.h>
#include <algorithm>
using namespace std;
int pre[100];
int score[100] ;//記錄各邊的名次，w[score[0]] 是最長的邊
int v[100],u[100],w[100];//分别存儲邊的兩個頂點，和權值
int cmp(const int i,const int j){ return w[i]<w[j];}
int findr(int x){
   int rx = pre[x];
   //找到根節點
   while (rx != pre[rx])
     rx = pre[rx];
    int tempx = x;
    while (pre[x]!=rx){
        tempx = x;
        x = pre[x];
        pre[tempx] = rx;
    }

    return rx;
   //優化

}

int mix (int a, int b){

   int ra = pre[a];
   int rb = pre [b];
   if (ra==rb)
    return 0 ;
   pre[rb] = ra ;
   return 1;
}
int main(){
   int m,n;

   while (scanf("%d%d",&m,&n)!=EOF && m){
    for (int i = 0 ; i < m ; i++){
        scanf("%d%d%d",&u[i],&v[i],&w[i]);
    }
    //初始化pre
     for (int i = 0 ; i < n ;i ++)
        pre[i] = i ;
     for(int i = 0 ; i < m ; i ++)
        score[i] = i ;
     //對各邊進行排序，将排序名次儲存在score中
     sort(score,score+m,cmp);
     //選擇n-1條邊
     int sum = 0;
     int side_num = 0;
     for (int i = 0 ; i < m ; i ++){
        int adj = score[i];
       // printf("adj = %d\n",adj);
        if (findr(u[adj]!=findr(v[adj]))){//如果該邊的兩個頂點的父節點不相同，即加入該邊後不會造成回路
                mix(u[adj],v[adj]);//将該邊加入最小生成樹
                sum+=w[adj];
                side_num++;
             //   printf("w = %d\n",w[adj]);
        }
        if (side_num>=n-1)//如果加入生成樹的邊大于等于n-1條
            break;
     }
     if (side_num<n-1)
        printf("?\n");
     else
     printf("%d\n",sum);
   }
  return 0;
}
           

輸出結果是最小生成樹的權值