Kruskal算法

紫书P356

这是最小生成树（也叫MST）的算法。

这里的这个排序cmp函数还是比较牛逼的，他是根据w的值排序得到w的下标递增值。

i.e.这个排序可以保留w数组不动，但又可以得到拍好序的下标值，存在r数组中。

#include 
    
     using namespace std;typedef long long ll;const int INF = 0x3f3f3f3f;#define cle(a,val) memset(a,(val),sizeof(a))#define SI(N) scanf("%d",&(N))#define SII(N,M) scanf("%d %d",&(N),&(M))#define SIII(N,M,K) scanf("%d %d %d",&(N),&(M),&(K))#define rep(i,b) for(int i=0;i<(b);i++)#define rez(i,a,b) for(int i=(a);i<=(b);i++)#define red(i,a,b) for(int i=(a);i>=(b);i--)const ll LINF = 0x3f3f3f3f3f3f3f3f;#define PU(x) puts(#x);#define PI(A) cout<<(A)<
     
      >n>>m){        for(int i=0;i
      
       >T;while(T--)    Solve();    return 0;}
      
     
    

以下是测试的数据：

输入

5 6

1 5 2

1 3 2

5 3 6

4 3 1

4 2 3

2 3 4

输出

0 1 2 3 4 5

3 0 1 4 5 2

8