そして集中の経路を調べて圧縮する.

回転:http://www.cnblogs.com/naix-x/archive/2012/06/13/2548228.html
 一番小さい木を作る時は、kruskyalで密集図を作ります.どのようにすべてタイムアウトですか?Primを試してみてもいいですか?期間の最適化の下で、そして集の部分を調べて、見た杭の電報の上のドキュメント、文書の上で言うのはとても良くて、2種類の方式を言いました.
   1.小さな木を大木に合併する.
   2.検索する時、木を圧縮しました.
   文書を見て話したほうがいいです..
   キーコード:

 1 int find(int x)//        

 2  {

 3      int i,r,j;

 4      r = x;

 5      while(r != o[r])//   

 6      {

 7          r = o[r];

 8      }

 9      i = x;

10      while (r != i)//              

11      {

12          j = o[i];

13          o[i] = r;

14          i = j;

15      }

16      return r;

17  }

18  void merge(int x,int y,int w)//           

19  {

20      x = find(x);

21      y = find(y);

22      if(x != y)

23      {

24          if(height[x] == height[y])//        

25          {

26              height[x] = height[x] + 1;

27              o[y] = x;

28          }

29          else if(height[x] < height[y])//                

30          {

31              o[x] = y;

32          }

33          else

34          o[y] = x;

35          min += w;

36          num ++;

37      }

38  }